MENU

【leetcode题解】反转链表

May 2, 2022 • 题解

所谓反转链表,就是对一个单向的链表进行反转,例如:

1->2->3->4->5->6

反转过后就是:

1<-2<-3<-4<-5<-6

那么这个该怎么做呢?

我们从题目中获取一些灵感吧

1.反转链表

题目链接:Leetcode 206.反转链表

通过题目可知,这个题其实并没有难度,只需要遍历一次链表,将其中的每一个节点都反转即可:

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

看完最基础的反转链表以后,我们再来看看更加高阶的反转链表问题

2.反转链表Ⅱ

题目链接:leetcode 92.反转链表Ⅱ

这个题与刚才的题目不同的是,本题是要实现链表的局部反转,我们从刚才的题目里已经学会了反转链表的方法,以此类推,我们看看能否将刚才的操作运用到这个题里面来

img

以上图为例,我们要反转这个局部的链表,实际上就是需要反转2->3->4这个子链表,因此我们需要做的事情是:

  1. 将子链表提出来
  2. 反转子链表
  3. 将子链表插回原链表中

因此,我们需要保存以下几个节点的信息:子链表前的一个节点(1号节点)、子链表的第一个节点(2号节点)、子链表的最后一个节点(4号节点),以及子链表的后一个节点(5号节点)。

首先,我们将子链表从这个链表中抽离,即断开1号节点与2号节点的连接,断开4号节点和5号节点之间的连接,然后将子链表反转,再将1号节点与4号节点相连,将2号节点与5号节点相连

看明白了过程我们就开始写代码了(注意:在这里我使用了一个幻影节点,用于减少不必要的分类讨论,例如如果要反转的首节点是第一个,那么就不需要再进行单独写代码进行讨论了):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* findNthNode(ListNode* head, int n) {
        // 遍历寻找该节点后的第n个节点
        ListNode* node = head;
        while (node->next != nullptr && n--) {
            node = node->next;
        }
        return node;
    }

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 1. 寻找断开节点1和2
        // 2. 断开节点 && 倒序排列节点
        // 3. 重新连接

        ListNode* shadowHead = new ListNode(0, head);

        if (head == nullptr || left == right) {
            return head;
        }
        
        // 寻找节点1和节点4
        ListNode* begin = findNthNode(shadowHead, left-1);
        ListNode* end = findNthNode(shadowHead, right);
        
        // 节点2和节点5
        ListNode* begin2 = begin->next;
        ListNode* end2 = end->next;

        // 断开节点
        begin->next = nullptr;
        end->next = nullptr;

        // 反转子链表
        ListNode* pre = nullptr;
        ListNode* cur = begin2;

        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        
        // 将子链表插回原链表中
        begin->next = end;
        begin2->next = end2;
        
        return shadowHead->next;
    }
};

3.K个一组反转链表

题目链接:leetcode 25. K 个一组翻转链表

这个题其实是反转链表Ⅱ的升级版,基本的思路还是反转链表的思路

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseListNode(ListNode* begin, ListNode* end) {
        // 这个部分和反转链表2的代码一样的
        ListNode* begin2 = begin->next;
        ListNode* end2 = end->next;

        begin->next = nullptr;
        end->next = nullptr;

        ListNode* pre = nullptr;
        ListNode* cur = begin2;

        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        begin->next = end;
        begin2->next = end2;

        return begin;
    }

    ListNode* findNthNode(ListNode* head, int n) {
        // 往后第n个节点
        while (head->next != nullptr && n--) {
            head = head->next;
        }
        return head;
    }

    int ListSize(ListNode* head) {
        // 获取链表的长度
        int ans = 1;
        while (head->next != nullptr) {
            head = head->next;
            ans++;
        }
        return ans;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || k == 1) {
            return head;
        }

        ListNode* shadowHead = new ListNode(0, head);
        int size = ListSize(head);
        size = size - (size % k);
        
        for (int i = 0; i < size; i += k) {
            // 挨个反转链表
            reverseListNode(findNthNode(shadowHead, i),
                            findNthNode(shadowHead, i + k));
        }

        return shadowHead->next;
    }
};
作者:NorthCity1984
出处:https://grimoire.cn/acm/reverse-listnode.html
版权:本文《【leetcode题解】反转链表》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任