题解 | 反转链表

描述

输入一个链表，反转链表后，输出新链表的表头。

方法一

1. 因为链表结尾是 null，所以让 pre 的值是 null, p 就表示我们的头部
   
2. 因为 p 的 next 成员马上就要指向 pre, 如果不保存 p 的下一个节点就会使其丢失，所以通过临时变量 t 保存它
   
3. 让 P 的 next 成员指向 pre
   
4. pre 移动到 p 的位置，p 移动到 t 的位置，此时我们就回到了第一步中的情况
   
5. 保持这个循环不变式直到 p 移动到原链表结尾我们就获得了翻转之后的链表。

   // c++
   class Solution {
   public:
    ListNode* ReverseList(ListNode* p) {
        ListNode* pre = nullptr;
        while (p) { // 判断链表是否已经到结尾
            ListNode* t = p->next; // 保留下一个即将翻转的表头
            p->next = pre; // 将现在要翻转的节点的后继指向前一个节点 pre
            pre = p; // 现在的 P 成为下一个前继节点
            p = t; // p 成为下一个要翻转的节点
        }
        return pre;
    }
   };

   # python3
   class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        pre = None
        cur = pHead
        while cur:
            tmp = cur.next # 保留下一个即将翻转的表头
            cur.next = pre # 将现在要翻转的节点的后继指向前一个节点 pre
            pre = cur # 现在的 P 成为下一个前继节点
            cur = tmp # p 成为下一个要翻转的节点
        return pre

   遍历一次链表，时间复杂度是 O(n)，空间复杂度是 O(1)。

   方法二

   如果上面的方法不便于理解，我们可以用数组把链表的每个元素都保存下来，翻转之后再重建链表，不过不推荐这种做法，它的时间复杂度是 O(n)， 空间复杂度是 O(n)。

   // c++
   class Solution {
   public:
    ListNode* ReverseList(ListNode* p) {
        if (!p) return p;
        vector<ListNode*> res;
        for (; p; p = p->next) {
            res.emplace_back(p); // 把每一个元素放入数组
        }
        reverse(res.begin(), res.end()); // 使数组取反
        for (int i = 0; i < res.size() - 1; i++) {
            res[i]->next = res[i + 1];  // 根据取反后的数组顺序重新构建链表
        }
        res[res.size() - 1]->next = nullptr; // 注意将最后一个元素的后继节点置为空，否则会出现环
        return res[0];
    }
   };

   # python3
   class Solution:
    # 返回ListNode
    def ReverseList(self, p):
        # write code here
        if not p: return p 
        res = []
        while p:
            res.append(p) # 把每一个元素放入数组
            p = p.next
        res = list(reversed(res))
        for i in range(len(res) - 1):
            res[i].next = res[i + 1] # 根据取反后的数组顺序重新构建链表
        res[-1].next = None # 注意将最后一个元素的后继节点置为空，否则会出现环
        return res[0]