LeetCode206.反转链表

题目

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

示例

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

思路

在遍历链表的的时候，修改当前结点的指针域的指向，让其指向它的前驱结点。为此需要用一个指针变量来保存前驱结点的地址。此外，为了在调整当前结点指针域的指向后还能找到后继结点，还需要另外一个指针变量来保存后继结点的地址，在所有结点都被保存好以后就可以直接完成指针的逆序了。

我之前也有写过单链表实现逆序的文章 ==> 链表实现逆序输出（改变链表结构）

Code

// 反转单链表函数
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;  // 保存当前节点的下一个节点
        curr->next = prev;  // 反转指针指向

        prev = curr;  // 更新 prev 指针为当前节点
        curr = nextTemp;  // 更新当前节点为下一个节点
    }

    return prev;  // prev 指向新的头节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

算法性能：链表逆序只需要对链表进行一次遍历，因此时间复杂度为O(n)，但是需要常数个额外的变量来保存当前结点的前驱结点与后继结点，因此时间复杂度为O(1).