【反转链表】【K个一组翻转链表】两个问题具体思路，文中含多种解法（附完整代码）

文章目录

• 前言
• 一、如何理解 反转链表？
• 二、反转链表
• • 1.方法一（递归）
  • 方法二（迭代）
• 三、K 个一组翻转链表

前言

本文将围绕【反转链表】问题展开详细论述。

采用【递归法】【迭代法】

同时，还将进一步升级该问题，讨论【K个一组翻转链表】

一、如何理解 反转链表？

题目链接: [点击跳转] Leetcode 206. 反转链表

二、反转链表

1.方法一（递归）

运用递归的方法来实现，首先我们应该考虑：递归哪个部分最终可以输出反转后的链表？

我们可以将递归函数内容设定为：每次递归将两个节点的连接方向反转。
比如原来1->2，现在变为2->1.

代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* tre = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tre;
    }
};
 

需要注意的是：在进入递归函数时，需要判断一下是否为空。

方法二（迭代）

使用迭代法就需要考虑：怎样去更新这个链表 或者 新建链表节点换序连接。

使用循环将所有节点都走一遍，那如何将两个节点换序呢？

1.定义三个节点，A,B,C，使A和B都指向头节点，C指向一个空节点

2.A先在链表上移动一位，将B指向C，此时将C与B同步（将C移到B处）

3.这时将B与A同步（将B移到A处）

完成以上三步就完成了一个循环，也就完成了两个节点方向的反转，一直重复这个循环。

代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

三、K 个一组翻转链表

题目链接: [点击跳转] Leetcode 25. K 个一组翻转链表

【K 个一组翻转链表】可以看作是【反转链表】的加强版，由原先的直接反转，变成给定的每k个节点反转一次。

因此，我们可以将问题拆解成：将长的链表每k个分成一组，然后把这一组反转，按序连接，不足k个的就直接连在最后。

创建一个哑节点 dummy 和一个指针 tail，用于构建结果链表。
使用 curr 指针遍历输入链表。

在每次循环中，首先确定一个长度为 k 的子链表的起始节点 sublistHead，然后通过计数确定是否有足够的 k 个节点。

如果有足够的节点（count == k），调用 reverseSublist 函数翻转这个子链表，并将翻转后的子链表连接到结果链表上，同时更新 tail 指针到新连接的子链表的末尾。

如果不足 k 个节点，直接将剩余的链表连接到结果链表上，并退出循环。
最后返回 dummy->next，即结果链表的头节点。

代码如下：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy;
        ListNode* curr = head;
        while (curr!= nullptr) {
            ListNode* sublistHead = curr;
            int count = 0;
            while (curr!= nullptr && count < k) {
                curr = curr->next;
                count++;
            }
            if (count == k) {
                ListNode* reversedSublist = reverseSublist(sublistHead, k);
                tail->next = reversedSublist;
                while (tail->next!= nullptr) {
                    tail = tail->next;
                }
            } else {
                tail->next = sublistHead;
                break;
            }
        }
        return dummy->next;
    }

    ListNode* reverseSublist(ListNode* head, int k) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        for (int i = 0; i < k; i++) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};