面试经典算法7-反转链表

LeetCode.206

问题描述

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

示例 1：

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

示例 2：

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

示例 3：

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

思路

这里给大家讲最经典的双指针法。

1. 如果链表为空或者只有一个节点，直接返回头结点head。
2. 初始化 pre 为 nullptr，cur 为头结点 head，node 为 cur 的下一个节点。
3. 在循环中，不断更新 pre、cur 和 node 的值，使得 cur 的 next 指向 pre，然后将 pre、cur 和 node 分别向后移动一位。
4. 当 cur 移动到链表末尾时，pre 就是反转后的新头结点。

演示过程：

初始状态：

第一步：

先定义一个空节点并初始化为nullptr，分别将这两个指针指向这个空节点和头结点，再定义一个节点用来临时存放节点。

ListNode* pre = nullptr; // 初始化 pre 为 nullptr

ListNode* cur = head; // 初始化 cur 为头结点

ListNode* node = nullptr; // 初始化 node 为 nullptr

第二步：

node = cur->next; // 保存当前节点的下一个节点

cur->next = pre; // 当前节点的 next 指向 pre，完成反转

第三步：

pre = cur; // 更新 precur = node; // 更新 cur

到这里，其实我们就可以使用一个循环，让继续这两步操作。不过为了大家更加看明白，我就将这个示例画完吧。

第四步：

node = cur->next; // 保存当前节点的下一个节点

cur->next = pre; // 当前节点的 next 指向 pre，完成反转

第五步：

pre = cur; // 更新 precur = node; // 更新 cur

第六步：

node = cur->next; // 保存当前节点的下一个节点

cur->next = pre; // 当前节点的 next 指向 pre，完成反转

第七步：

pre = cur; // 更新 precur = node; // 更新 cur

第八步：

node = cur->next; // 保存当前节点的下一个节点

cur->next = pre; // 当前节点的 next 指向 pre，完成反转

第九步：

pre = cur; // 更新 precur = node; // 更新 cur

第十步：

node = cur->next; // 保存当前节点的下一个节点

cur->next = pre; // 当前节点的 next 指向 pre，完成反转

第十一步：

pre = cur; // 更新 precur = node; // 更新 cur

此时cur==nullptr，退出循环。

参考代码

C++

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head; // 如果链表为空或者只有一个节点，直接返回头结点
        }

        ListNode* pre = nullptr; // 初始化 pre 为 nullptr
        ListNode* cur = head; // 初始化 cur 为头结点
        ListNode* node = nullptr; // 初始化 node 为 nullptr

        while (cur != nullptr) {
            node = cur->next; // 保存当前节点的下一个节点
            cur->next = pre; // 当前节点的 next 指向 pre，完成反转
            pre = cur; // 更新 pre
            cur = node; // 更新 cur
        }

        return pre; // pre 就是反转后的新头结点
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    Solution solution;
    ListNode* newHead = solution.reverseList(head);

    while (newHead != nullptr) {
        std::cout << newHead->val << " ";
        newHead = newHead->next;
    }

    return 0;
}

Java

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 如果链表为空或者只有一个节点，直接返回头结点
        }

        ListNode pre = null; // 初始化 pre 为 null
        ListNode cur = head; // 初始化 cur 为头结点
        ListNode node = null; // 初始化 node 为 null

        while (cur != null) {
            node = cur.next; // 保存当前节点的下一个节点
            cur.next = pre; // 当前节点的 next 指向 pre，完成反转
            pre = cur; // 更新 pre
            cur = node; // 更新 cur
        }

        return pre; // pre 就是反转后的新头结点
    }
}

public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        Solution solution = new Solution();
        ListNode newHead = solution.reverseList(head);

        while (newHead != null) {
            System.out.print(newHead.val + " ");
            newHead = newHead.next;
        }
    }
}

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head  # 如果链表为空或者只有一个节点，直接返回头结点

        pre = None  # 初始化 pre 为 None
        cur = head  # 初始化 cur 为头结点
        node = None  # 初始化 node 为 None

        while cur is not None:
            node = cur.next  # 保存当前节点的下一个节点
            cur.next = pre  # 当前节点的 next 指向 pre，完成反转
            pre = cur  # 更新 pre
            cur = node  # 更新 cur

        return pre  # pre 就是反转后的新头结点

head = ListNode(1, ListNode(2, ListNode(3)))
solution = Solution()
new_head = solution.reverseList(head)
while new_head is not None:
    print(new_head.val, end=" ")
    new_head = new_head.next