LeetCode025之K 个一组翻转链表（关话题：递归，链表逆序）

题目描述：

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

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

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

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换

解题思路

解法一

1、 先反转以 head 开头的 k 个元素。

2、 将第 k + 1 个元素作为 head 递归调⽤ reverseKGroup 函数。

3、如果最后的元素不⾜ k 个， 就保持不变

解法二

看图写代码

1.为了代码的可读性，定义一个虚拟指针dummy作为head的前驱指针

2.初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾

3.start和next是while循环内的局部变量分别对应 pre 和 end的后继指针

代码实现

解法一：

先要理解下单链表的逆序算法:漫画：如何将一个链表“逆序”？ - 知乎,然后理解如下代码

package com.lzhsite.leetcode.algoritom.practise.linked;

import com.lzhsite.leetcode.algoritom.dataStruct.DLNode;

public class LeetCode025K个一组翻转链表 {

	/** 反转区间 [a, b) 的元素， 注意是左闭右开 */
	DLNode reverse(DLNode a, DLNode b) {
		ListNode p1, p2, p3;
		p1 = a;
		p2 = a.next;
		p3 = null;
		// while 终⽌的条件改⼀下就⾏了
		while (p2 != b) {
			p3 = p2.next;
			p2.next = p1;
			p1 = p2;
			p2 = p3;
		}
		// 返回反转后的头结点
		return p1;
	}

	DLNode reverseKGroup(DLNode head, int k) {
		if (head == null)
			return null;
		// 区间 [a, b) 包含 k 个待反转元素
		DLNode a, b;
		a = b = head;
		for (int i = 0; i < k; i++) {
			// 不⾜ k 个， 不需要反转， base case
			if (b == null)
				return head;
			b = b.next;
		}
		// 如何k个⼀组反转链表
		// 反转前 k 个元素
		DLNode newHead = reverse(a, b);
		// 递归反转后续链表并连接起来
		a.next = reverseKGroup(b, k);
		return newHead;
	}
}

解法二:

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;

    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) end = end.next;
        if (end == null) break;
        ListNode start = pre.next;
        ListNode next = end.next;
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
        pre = start;

        end = pre;
    }
    return dummy.next;
}

private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}