signed

QiShunwang

“诚信为本、客户至上”

【icyle】Leetcode-cn:25. K 个一组翻转链表

2021/3/21 10:40:46   来源:

题目

解答:分解成一组k个的小问题

思路

就像解答所说,定义一个负责解决一组k个的小问题的函数,这个函数在以后能够直接解决反转链表这一题目。
简单描述一下反转链表如何实现:

  1. 这一条子链表的最后一个元素的next(也就是下一条子链表的的第一个元素)定义为prev结点;
  2. 这一条子链表的第一个元素定义为ptr结点;
  3. 这一条子链表的第二个元素定义为nextptr结点;
  4. ptr下一个接上prev,prev结点变为ptr,ptr结点变为nextptr。(相当于对这一条子链表来说,这三个指针全部循环向前走了一位,同时还让第一个结点指向了下一组的第一个结点,完成了反转链表的关键一步)
  5. 重复1-4,至prev指向为最后一个元素时结束(指向最后一个元素说明该组链表已经遍历了一圈)。

剩下的工作就是上一组链表接上这一组链表(因为我们刚刚做的只是这一组链表接上下一组链表),同时dummy和head指针移动一下,为下一组链表反转定好位置。

代码
/*
 * @lc app=leetcode.cn id=25 lang=cpp
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * 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) {}
 * };
 */
//utility在一些比较常用的vector、iostream等头文件中都有包含,此处仅说明pair包含在utility头文件中
#include <utility>
//tie同上
#include <tuple>
using namespace std;
class Solution
{
public:
    // 翻转一个子链表,并且返回新的头与尾
    //此部分用图形画出展示会更清楚
    pair<ListNode *, ListNode *> myReverse(ListNode *head, ListNode *tail)
    {
        ListNode *prevptr = tail->next;
        ListNode *ptr = head;
        while (prevptr != tail)
        {
            ListNode *nextptr = ptr->next;
            ptr->next = prevptr;
            prevptr = ptr;
            ptr = nextptr;
        }
        return {tail, head};
    }

    ListNode *reverseKGroup(ListNode *head, int k)
    {
        //定义一个头指针指向头结点,最后返回的时候用
        ListNode *preHead = new ListNode(0);
        preHead->next = head;
        //复制一份,因为preHead也是要改的,就用这份movehead来改
        ListNode *movehead = preHead;

        while (head)
        {
            //定义前一组结点的尾巴(比如第二组的456,前一组的3就是tail指向的结点)
            ListNode *tail = movehead;
            //既然都定义了,就先找到tail结点
            for (int i = 0; i < k; i++)
            {
                tail = tail->next;
                if (!tail)
                {
                    return preHead->next;
                }
            }
            //这一步原本是有的,但是reverse那里已经做了,就不要重复了
            //那么顺带下面有关nexthead的也不需要用到了
            //找到了tail,待会tail要被替换顺序的,现在先存好下一组的头结点
            //ListNode *nexthead = tail->next;

            //现在可以开始反转结点了
            tie(head, tail) = myReverse(head, tail);

            // 把子链表重新接回原链表
            // 记得,现在的head是原来的tail,已经反过来了
            //现在,做两项工作,使得下一次循环是正确的
            //1. 连接前后两组子链表:头指针接上原来的尾巴,原来的尾巴接到下一组第一个头结点上
            movehead->next = head;
            // tail->next = nexthead;

            //2.改movehead位置:头指针指向这一组的最后一个,使得next就是下一组第一个头结点
            //改head位置,使得head永远在movehead后一个
            movehead = tail;
            head = tail->next;
        }

        //跳出循环证明结束了,返回头结点即可
        return preHead->next;
    }
};
// @lc code=end
时间复杂度和空间复杂度
  • 时间复杂度: O(n) 。其中 n 是链表的节点数量。由于成组递归,每组k个,所以最终递归次数不超过 n k \frac{n}{k} kn,每次对组内k个结点进行操作,渐进时间复杂度即为 O(n)
  • 空间复杂度:O(1)

反思与总结

重点掌握反转链表。