题目
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。


解析思路
1.通过找到start和end的区间,通过遍历寻找k个节点,也就是end的位置。
2.end的末尾截断,然后头插法反转start,end区间的链表。
3.通过新的链表接收这个反转区间
4.如果没有k的倍数,就直接跳出,然后pre指向start,也就是未处理的部分。
5.返回dummy即可。
代码
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| public class P25 {
public static void main(String[] args) { ListNode head=new ListNode(0); ListNode cur=head; for(int i=1;i<=5;i++){ cur.next=new ListNode(i); cur=cur.next; } head=head.next; P25 p25 = new P25(); ListNode node = p25.reverseKGroup(head, 3); while (node!=null){ System.out.println(node.val); node=node.next; } }
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null||head.next==null){ return head; }
ListNode dummy=new ListNode(-1); ListNode pre=dummy; ListNode start=head; ListNode end=head;
while(end!=null){ for(int i=1;i<k&&end!=null;i++){ end=end.next; } if(end==null){ break; } ListNode next =end.next; end.next=null; pre.next=reverse(start); pre=start; start=next; end=next; } pre.next=start; return dummy.next; }
private ListNode reverse(ListNode start) { ListNode pre=null; ListNode cur=start;
while (cur!=null){ ListNode next=cur.next; cur.next=pre; pre=cur; cur=next; }
return pre; } }
|
总结
时间复杂度最坏是O(n2),两个循环,然后空间复杂度是O(1),只使用了几个常量节点。这道题就是模拟就行,我看其他人还使用递归,这个后面看看。