剑指 Offer 24. 反转链表

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

题目描述

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

示例1:

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

限制:

0 <= 链表长度 <= 10000

思路分析1

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

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

算法过程

  • 第一,首先应该判断其 head 指针是否为空,也就是 NULL。如果是 NULL,则直接返回。
  • 第二,创建两个指针 formerlatter 分别指向当前头指针(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 = latterlatter = 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中的方法类似,只不过双指针法是 formerlatter 结点之间的 next 指针的变化。而解法2中的方法没有增加 temp 指针来保存原链表的位置,而是直接使用了三个已经确定的指针,其中 temp 指针直接使用了 head 指针来代替。此方法也叫 头插法。

算法过程

  • 第一,令 formerlatterNULL
  • 第二,while 循环,终止条件是 head 等于 NULL
  • 第三,将 latterhead 向后递进一个结点,也就是 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;
    }
};

类似文章

订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论