记录生活中的点点滴滴

0%

K个一组反转链表

leetcode上的题目:K 个一组翻转链表

结合刚刚总结的一些反转链表的方法,拿下这道题,做一下巩固。

K个一组反转链表:

1
2
3
public ListNode reverseKGroup(ListNode head,int k){

}

拿到这道题,我们先看看能不能用递归解决?

上面这个函数的作用是输入一个链表头结点和k,完成要求的功能,返回之后的链表的头结点。

仔细想想,是可以使用递归的,假设头结点是a,下一个需要反转的头结点是b(其实就是上图中的3)。

那么对于b及其之后的,我们都可以使用 reverseKGroup(b,k) 这个原本函数的递归去解决。

所以关键就是怎样将 前面k个节点 和 b之后的链表 两者连接起来。

对于前面k个节点,其实就是使用一个迭代改变指针指向即可。

我们先看看我们之前写的使用迭代改变指针反转整个链表的函数:

1
2
3
4
5
6
7
8
9
10
11
12
//迭代改变指针法
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while(curr!=null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}

循环退出的条件是curr指向空,那么如果对于 reverse(ListNode a, ListNode b) ,它反转a到b(左闭右开,不包括b)的退出条件呢?

其实就是 curr!=b ,替换一下即可。

不过注意只返回区间 [a, b) 的元素,从b的前一个节点到a。

这样正好也符合题意,对于这个返回的新的头结点,和reverse(ListNode a, ListNode b) 递归得到的一个节点,这两者是什么关系?

其实就是新节点的next等于后面,这样就将两者连接起来了。

所以总的代码如下:

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
class Solution {
/** 反转区间 [a, b) 的元素,注意是左闭右开 */
//注意只返回区间 [a, b) 的元素,从b的前一个节点到a
public ListNode reverse(ListNode a, ListNode b){
ListNode curr = a;
ListNode prev = null;
while (curr!=b){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}

public ListNode reverseKGroup(ListNode head,int k){
ListNode a,b;
a = b = head;
for (int i = 0; i < k; i++) {
//不足k个,什么都不敢直接返回head
if(b==null) return head;
b = b.next;
}
//先反转前面k节点
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b,k);
return newHead;
}
}