算法通关村第二关终于学会链表反转了

手写链表反转

建立虚拟头结点辅助反转

题目 LeetCode 206

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode reverseList(ListNode head) {
    
    }
}

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

分析

这种题，给你链表的头结点head

最好不要去用head结点遍历，自己创建个cur节点指向head

在遍历过程中修改 cur 的指向，不会影响原始的头节点head，防止链表出错

再创建一个虚拟节点dummy方便返回修改后链表的头结点

学了那么多的技巧：

• 要遍历链表，就要创建一个指针去单独遍历
• 要返回修改后的头结点，就要创建一个虚拟节点去返回

最好不要动题目一开始就给你的head头结点

遍历是这样的：

用cur去遍历，找到一个节点A，虚拟头结点就指向它

同时虚拟头结点之前指向的要跟在当前cur指向的A后面

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        //创建虚拟头结点
        ListNode ans = new ListNode(0);
        //创建节点cur指向头结点head
        ListNode cur = head;  
        while (cur != null) {  
            //临时存储cur指针的下一个结点
            ListNode nextTemp = cur.next;  
            //让cur指针指向prev
            cur.next = ans.next;  
            //将prev变量的值更新为当前curr的值
            //以便下一次循环做准备
            ans.next = cur;
            curr = nextTemp;  
        }  
        return ans.next;  
    }
}

1. ListNode ans = new ListNode(0); 这里创建了一个新的链表节点 ans，并将其初始化为0。这个节点实际上是一个虚拟的头节点，它的存在使得在反转链表后，链表的第一个元素可以指向正确的值。
2. ListNode cur = head; 这里创建了一个指针 cur，并将其指向输入的链表的头节点 head。
3. while (cur != null) {...}: 这是一个循环，它将遍历输入的链表，直到 cur 变为 null。
4. ListNode nextTemp = cur.next; 在循环内部，创建一个临时变量 nextTemp 来保存 cur 的下一个节点，这是因为在后面的步骤中，我们会修改 cur.next，如果直接使用 cur.next，那么在下一次循环中就无法访问到正确的下一个节点了。
5. cur.next = ans.next; 这行代码是反转链表的关键步骤。它将 cur 的 next 指针指向 ans.next，这实际上是将 cur 移动到了它原本应该处于的位置。
6. ans.next = cur; 这行代码将当前节点 cur 添加到新链表的头部。
7. curr = nextTemp; 在完成一次循环后，更新 cur 为 nextTemp，以便下一次循环可以正确进行。
8. return ans.next; 当循环结束时，返回的是新链表的头节点（即原链表的最后一个节点）。

---

直接操作链表实现反转

题目

要求以不创建一个虚拟节点为前提，直接作为头结点作为输入，去反转链表，输出反转后的链表头结点

分析

不是使用虚拟节点的话，就在遍历链表的过程中，逐步修改每个节点的next指针，使其指向上一个节点，从而反转链表

代码

class Solution {  
    public ListNode reverseList(ListNode head) {  
        //创建变量prev初始为空
        ListNode prev = null;
        //创建变量curr初始化为输入的链表头结点
        ListNode curr = head;  
        while (curr != null) {  
            ListNode nextTemp = curr.next;  
            //把curr的next指针修改指向prev
            //即当前结点指向上一个结点
            curr.next = prev;  
            //prev更新为cur
            prev = curr;  
            //curr更新为next
            curr = nextTemp;  
        }  
        //循环结束，prev为新链表头结点
        return prev;  
    }  
}