100道面试必会算法-反转链表-02

100道面试必会算法-反转链表-02

反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

定义两个指针 cur 和 pre，分别指向当前节点和前一个节点。初始时，cur 指向头节点 head，pre 为 null

• 创建一个临时节点 temp，用于保存当前节点的下一个节点。
• 将当前节点的 next 指针指向前一个节点 pre，实现反转。
• 更新 pre 为当前节点 cur，表示当前节点已经处理完毕，向后移动一位。
• 更新 cur 为之前保存的临时节点 temp，继续处理下一个节点。

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        // 定义当前节点cur和前一个节点pre，初始时cur指向头节点，pre为null
        ListNode cur = head, pre = null;
        
        // 遍历链表直到当前节点为null（即链表末尾）
        while (cur != null) {
            // 保存当前节点的下一个节点，以防丢失
            ListNode temp = cur.next;
            
            // 将当前节点的next指针指向前一个节点，实现反转
            cur.next = pre;
            
            // 更新pre为当前节点，cur指向之前保存的下一个节点
            pre = cur;
            cur = temp;
        }
        
        // 循环结束后，pre指向反转后的链表的头节点
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

   // 循环结束后，pre指向反转后的链表的头节点
    return pre;
}
1
2
3

}

1