当前位置：首页 > news >正文

面试热题（翻转k个链表）

news 2025/8/16 3:22:50

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

对链表进行k个节点的反转，首先我们要先知道链表的节点个数有多少个？才能知道我们需要翻转多少次？最后不够的节点是不需要翻转的

        int n=0;ListNode cur=head;//计算出列表的长度while(cur!=null){n++;cur=cur.next;}

为了使head节点不具有特殊性，我们经常会在head节点前加一个虚拟头结点dummyHead

过程如下：

序号12345的代码：

  for (int i =0; i <k; i++) {ListNode next=curNode.next;curNode.next=pre;pre=curNode;curNode=next;}

序号67的代码：

           ListNode next=p0.next;p0.next.next=curNode;p0.next=pre;p0=next;

通过while的循环，就可以将k个节点进行反转，多指针这种方法也是比较好想的，但是就是比较容易绕，希望大家可以看着我画的图进行理解

源代码：

 public ListNode reverseKGroup(ListNode head, int k) {if(head==null){return null;}int n=0;ListNode cur=head;//计算出列表的长度while(cur!=null){n++;cur=cur.next;}ListNode dummyNode=new ListNode(-1);dummyNode.next=head;ListNode pre=null;ListNode p0=dummyNode;ListNode curNode=p0.next;while(n>=k){n-=k;for (int i =0; i <k; i++) {ListNode next=curNode.next;curNode.next=pre;pre=curNode;curNode=next;}ListNode next=p0.next;p0.next.next=curNode;p0.next=pre;p0=next;}return dummyNode.next;}

下面给大家递归的代码，供大家借鉴：

   //递归反转public ListNode reverseKGroup(ListNode head, int k) {if(head==null||head.next==null){return head;}ListNode r=head;for (int i = 0; i <k; i++) {if(r==null){return head;}r=r.next;}ListNode node=reverse(head,r);head.next=reverseKGroup(r,k);return node;}//给定区间链表进行反转public ListNode reverse(ListNode head,ListNode right){ListNode pre=null,curNode=head,next=null;while(curNode!=right){next=curNode.next;curNode.next=pre;pre=curNode;curNode=next;}return pre;}

查看全文

http://www.lryc.cn/news/115862.html