链表中的节点每k个一组翻转

在这里插入图片描述

代码求解

要实现每k个一组翻转链表，我们先来手撕一下反转整个链表：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


//反转以a为头节点的链表
	ListNode reverse(ListNode a){
		ListNode pre = null;
		ListNode cur = a;
		ListNode next = a;
		while(cur!=null){
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}

我们再来手撕一下反转a到b之间的节点：

注意是左闭右开区间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


//反转区间[a,b)的节点
	ListNode reverse(ListNode a,ListNode b){
		ListNode pre = null;
		ListNode cur = a;
		ListNode next = a;
		while(cur!=b){
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}

所以，实现每k个一组反转就是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


ListNode reverseKGroup(ListNode head,int k){
		if(head == null){
			return null;
		}

		ListNode a = head;
		ListNode b = head;

		for(int i=0;i<k;i++){
			if(b==null){
				return head;
			}
			b=b.next;
		}
		//反转[a,b)区间的链表，得到新的头节点
		ListNode newHead = reverse(a,b);
		//递归处理剩余区间，拼接链表
		a.next = reverseKGroup(b,k);
		return newHead;
	}


	ListNode reverse(ListNode a,ListNode b){
		ListNode pre = null;
		ListNode cur = a;
		ListNode next = a;
		
		while(cur!=b){
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}

		return pre;
	}