剑指 Offer 24. 反转链表

剑指 Offer 24. 反转链表题目链接：剑指 Offer 24. 反转链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例1：

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

限制：

0 <= 链表长度 <= 10000

思路分析1

此题目是一道经典的算法题，即反转链表。

首先应该想到的是，遍历链表，逐个更改链表节点的 next 指针。为了在更改之后不丢失原来链表（即还能够找到之前的链表），所以还需要一个临时指针 temp 。此方法也是最常用的一种。

算法过程

• 第一，首先应该判断其 head 指针是否为空，也就是 NULL。如果是 NULL，则直接返回。
• 第二，创建两个指针 former 和 latter 分别指向当前头指针（head）和下一个指针（head->next）。
• 第三，使用 while 循环遍历链表，终止条件为：latter 等于 NULL 的时候。
• 第四，在 while 循环中，由于我们需要更改 latter 的 next，使其指向 former ，也就是前一个结点，那么这样势必会失去原链表的位置，原链表也就变得不可获取了。为了解决这个问题，所以我们要创建一个临时指针，来提前保存 latter 的 next 指针，这样就不会因为改变了 latter 的 next 指针而失去整个链表。也就是 ListNode* tmp = latter->next.
• 第五，将 latter 的下一个指针指向前一个结点 former，就是 latter->next = former。
• 第六，重新将 former 和 latter 赋值为正确的位置，就是 former = latter 和 latter = tmp.
• 第七，最后看只需将现在链表的最后一个结点，也就是 head->next = NULL，接完成了链表的反转。

代码

经典的双指针法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL)
            return NULL;
        ListNode* former = head;
        ListNode* latter = head->next;
        while (latter != NULL) {
            ListNode* tmp = latter->next;
            latter->next = former;
            former = latter;
            latter = tmp;
        }
        head->next = NULL;
        return former;
    }
};

思路分析2

此方法和思路1中的方法类似，只不过双指针法是 former 和 latter 结点之间的 next 指针的变化。而解法2中的方法没有增加 temp 指针来保存原链表的位置，而是直接使用了三个已经确定的指针，其中 temp 指针直接使用了 head 指针来代替。此方法也叫 头插法。

算法过程

• 第一，令 former 和 latter 为 NULL
• 第二，while 循环，终止条件是 head 等于 NULL
• 第三，将 latter 和 head 向后递进一个结点，也就是 latter = head, head = head->next。需要注意的是，head 指针永远比 latter 大一个结点，就是 head 结点在 latter 结点的后面。而 head 指针的作用就是为了能够在变换 latter 的 next 之后，仍能找到原链表。
• 第四，修改 latter 的 next 指针，使其指向 former
• 第五，递增 former，就是令 former = latter，使其向后一个结点。
• 第六，while end
• 第七，返回 former 或者 latter 指针。

说明

此方法不需要在循环之后，另行指定新链表最后一个结点的 next 指针。这是因为在第一次 while 循环中，其已经被指定。

所谓头插法，只不过只用了显式的 head 指针来代替 temp（思路一），防止丢掉链表。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* former = NULL;
        ListNode* latter = NULL;
        while (head != NULL) {
            latter = head;
            head = head->next;
            latter->next = former;
            former = latter;
        }
        
        return former;
    }
};