LeetCode206.反转链表

题目

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

示例

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

思路

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

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

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 指向新的头节点}

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