LeetCode 25. K 个一组翻转链表 && 链表反转

2023-09-28 17:18:34

题目要求

原题目链接：25. K 个一组翻转链表

这里是引用

题目要求如下：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例如下：

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

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

ListNode节点结构如下：

  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

解法：模拟，原地反转

思路

首先观察问题描述，不难发现问题的核心就是链表的原地反转，找到了问题的核心，便可以对原问题进行分解，在整个反转过程中会经历若干次部分节点的反转，我们把每次将要反转的若干节点都当作一个单链表处理，问题的解决便可以分解为以下两个步骤：

单链表反转。
反转后链表与原链表衔接。

单链表反转

单链表反转思路不熟悉的读者可以查阅相关资料，笔者文章推送Java反转链表的两种方式

暂不考虑题目，单链表的原地反转的核心代码如下：

	public static Node reverse(Node head){
        Node p = head;
        Node q = null;
        Node temp = null;
        while(p != null){
  			// 先获取下一个要遍历的节点
            q = p.next;
            // 改变p的指向为next next为当前遍历到的节点的上一个节点 初始为null
            p.next = temp;
            // 记录next为当前节点 到下一次遍历 next的指向就是所谓的当前节点的上一个节点
            temp= p;
            // p指向下一个要遍历的节点 后进入下一次循环
            p = q;
        }
        return next;
    }

在本题目的场景下需要对方法做出修改，主要体现在单链表反转时，初始尾节点的next节点为null，而在本题目场景下，初始尾节点的next节点是原链表的剩余部分，因此需要将原链表剩余部分的首节点作为参数传递给链表反转方法。

针对本题目修改后链表逆转方法如下：

其中入参head为将要反转的部分链表的首节点，入参tail为原链表中将要反转的部分链表后的第一个节点，同时要将逆转后的首节点作为返回值返回，以便后续衔接。

	public ListNode reverse(ListNode head, ListNode tail){
        ListNode p = head;
        ListNode q = null;
        ListNode temp = tail;
        while(p != tail){
            q = p.next;
            p.next = temp;
            temp = p;
            p = q;
        }
        return temp;
    }

此步骤执行示意图如下：

与原链表衔接

原链表衔接分为两个部分，逆转部分与其前面的链表连接，即逆转后部分节点的尾节点最后要指向原链表的后半部分，和逆转部分与其后面的链表连接，即原链表前半部分的尾节点最后要指向被逆转的部分节点的首节点。

在单链表反转中已经做完了一半衔接工作——即与后半部分链表连接，那么现在只需要处理前半部分与逆转链表连接即可。

思路非常简单，只需要在逆转链表前保存逆转部分的前面第一个节点即可（本文记该节点为hair），随后使该节点.next = 逆转部分首节点，一次原链表内的部分节点逆转就完成了。

示意图如下：

完整AC代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);// 需要一个头节点 辅助第一次逆转和结果返回
        ListNode res = dummy; // 用作结果返回
        while(true){
            ListNode hair = dummy;
            // 此循环是为了找到后半部分的首个节点 即tail节点
            for(int i = 0; i < k; i++){
                if(dummy.next != null){
                    dummy = dummy.next;
                }else{
                	//剩余节点不足k个 意味着全部反转完成 返回链表即可
                    return res.next;
                }
            }
            ListNode tail = dummy.next;
            hair.next = reverse(hair.next, tail);
            // 因为dummy被反转了 所以dummy在原链表中的实际位置前移了k-1位 现在要向后移回
            for(int i = 0; i < k - 1; i++) dummy = dummy.next;
        }
    }
    public ListNode reverse(ListNode head, ListNode tail){
        ListNode p = head;
        ListNode q = null;
        ListNode temp = tail;
        while(p != tail){
            q = p.next;
            p.next = temp;
            temp = p;
            p = q;
        }
        return temp;
    }
}

复杂度分析

时间复杂度：O(n)，n为原链表的总长度，链表会反转n/k次，每次进行时间复杂度为O(k)的反转，遍历的时间复杂度为一次遍历O(n)加上每次逆转后的dummy移回，O(n/k * (k - 1))，均为O(n)级别。
空间复杂度：O(1)，只额外使用了常数个变量。

码农公寓