剑指offer | 24. 反转链表

你的名字 2022-12-27 04:48 165阅读 0赞

**题目内容：**

> 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

**示例:**

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

**方法一：双指针迭代**

*  两个指针一前一后移动，后面的指针不断讲链表后面结点的指针反向，直到结束。
 *  时间复杂度O(N)：遍历链表使用线性大小时间
 *  空间复杂度O（1）：变量pre和cur使用常熟大小额外空间。

class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            ListNode *cur = head, *pre = nullptr;
            while(cur != nullptr) { 
                ListNode* tmp = cur->next; // 暂存后继节点 cur.next
                cur->next = pre;           // 修改 next 引用指向
                pre = cur;                 // pre 暂存 cur
                cur = tmp;                 // cur 访问下一节点
            }
            return pre;
        }
    };

**方法二：递归**

*  递归法遍历链表，当越过尾结点后种止递归，在回溯时修改各结点的`next`引用指向。
 *  recur(cur,pre)递归函数：
    
     *  终止条件：当cur为空，则返回尾结点pre（即反转链表的头节点）
     *  递归后继结点，记录返回值（即反转链表的头节点）为res；
     *  修改当前结点cur引用指向前驱结点pre
     *  返回反转链表头节点res；
 *  reverseList（head）函数：
 *  调用并返回recur（head，null）。传入null是因为反转链表后，head结点指向null。
 *  时间复杂度O(N):遍历链表使用线性大小时间。
 *  空间复杂度O(N):遍历链表递归深度达到N，系统使用O（N）大小的额外空间。

class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            return recur(head, nullptr);           // 调用递归并返回
        }
    private:
        ListNode* recur(ListNode* cur, ListNode* pre) { 
            if (cur == nullptr) return pre;        // 终止条件
            ListNode* res = recur(cur->next, cur); // 递归后继节点
            cur->next = pre;                       // 修改节点引用指向
            return res;                            // 返回反转链表的头节点
        }
    };

参考：[剑指 Offer 24. 反转链表（迭代 / 递归，清晰图解）][Offer 24. _ _]

[Offer 24. _ _]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/jian-zhi-offer-24-fan-zhuan-lian-biao-die-dai-di-2/