[关闭]
@yexiaoqi 2022-05-30T08:37:33.000000Z 字数 1311 阅读 280

25. K 个一组翻转链表

刷题 leetcode


题目:给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。算法空间复杂度:O(1)
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

难度:困难

示例1

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

示例2

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

提示
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

链接https://leetcode.cn/problems/reverse-nodes-in-k-group


  1. class Solution {
  2. //单链表
  3. public class ListNode {
  4. int val;
  5. ListNode next;
  6. ListNode() {}
  7. ListNode(int val) {this.val = val;}
  8. ListNode(int val, ListNode next) {this.val = val;this.next = next;}
  9. }
  10. public ListNode reverseKGroup(ListNode head, int k) {
  11. ListNode dump = new ListNode(0);
  12. //将伪节点与链表头节点相连 dump->1->2->3->4
  13. dump.next = head;
  14. //要反转的链表的头尾节点
  15. ListNode prev = dump;//pre指向每次要翻转的链表头节点的上一个节点
  16. ListNode end = dump;//end指向每次要翻转的链表尾节点
  17. while(end.next != null){
  18. //循环k次,将end向后移动k个节点,找到需要翻转的链表的结尾
  19. for (int i=0; i<k && end!=null; i++) {
  20. end = end.next;
  21. }
  22. if (end==null) break;
  23. ListNode thisHead = prev.next;//记下要翻转链表的头节点
  24. ListNode nextHead = end.next;//记下链表尾节点的next,方便后面链接链表
  25. end.next = null;//断开链表
  26. prev.next = reverse(thisHead);//翻转,然后prev.next指向头节点
  27. thisHead.next = nextHead;//翻转后头节点变为尾节点,通过.next把断开的链表重新链接
  28. prev = thisHead;//prev和end设置为下次要翻转的链表头节点的上一个节点,类似dump
  29. end = prev;
  30. }
  31. return dump.next;
  32. }
  33. //迭代法:一个一个反转
  34. public ListNode reverse(ListNode head) {
  35. ListNode prev = null;
  36. ListNode curr = head;
  37. while (curr != null) {
  38. ListNode tmp = curr.next; //记录当前节点的下一个节点
  39. curr.next = prev; //反转
  40. prev = curr; //prev和curr节点都前移一位
  41. curr = tmp;
  42. }
  43. return prev; //此时prev移动到了原链表的尾部,即反转后链表的首部,所以返回
  44. }
  45. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注