反转链表：迭代递归头插

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

需求

• 反转链表并输出

实现

• 迭代
• 递归
• 头插

思考

说来惭愧，七七竟然想要：：-1来实现，学python学傻了

代码

• 迭代

public class Solution {
    public ListNode reverseList(ListNode head) {
//        迭代法
//        当前字为引令，当前节点的下一个节点为next，迭代过程中，将当前节点的next指向前一个节点
//        下一个节点为当前节点的next
        ListNode prev = null;
        ListNode current = head;
        ListNode next = head.next;

        while (current != null) {
            current.next = prev;
            prev = current;
            current = current.next;
        }

        return prev;
    }
}

• 递归

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        // 递归终止：空节点 或 走到最后一个节点
        if (head == null || head.next == null) {
            return head;
        }
        // 递归深入，拿到反转后的新头结点
        ListNode newHead = reverseList(head.next);

        // 反转指针：后继节点指向当前节点
        head.next.next = head;
        // 断开原指向，防止链表成环
        head.next = null;

        // 始终返回新头结点
        return newHead;
    }
}

• 头插

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(-1); // 虚拟头节点
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next; // 1. 暂存后继
            cur.next = dummy.next;     // 2. cur 指向已反转部分
            dummy.next = cur;           // 3. cur 插到 dummy 后面
            cur = next;                 // 4. 处理下一个
        }
        return dummy.next;
    }
}

竟然有三个方法，那我们平时怎么选择呢？

关键总结

1. 迭代法：效率最高，面试首选，空间复杂度 O (1)
2. 递归法：代码简短，逻辑抽象，长链表可能栈溢出
3. 头插法：扩展性强，常用于「链表区间翻转」题型

‍