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

# 25. K 个一组翻转链表

刷题 leetcode

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



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



1 <= k <= n <= 5000
0 <= Node.val <= 1000

class Solution {    //单链表    public class ListNode {        int val;        ListNode next;        ListNode() {}        ListNode(int val) {this.val = val;}        ListNode(int val, ListNode next) {this.val = val;this.next = next;}    }    public ListNode reverseKGroup(ListNode head, int k) {        ListNode dump = new ListNode(0);        //将伪节点与链表头节点相连  dump->1->2->3->4        dump.next = head;        //要反转的链表的头尾节点        ListNode prev = dump;//pre指向每次要翻转的链表头节点的上一个节点        ListNode end = dump;//end指向每次要翻转的链表尾节点        while(end.next != null){            //循环k次，将end向后移动k个节点，找到需要翻转的链表的结尾            for (int i=0; i<k && end!=null; i++) {                end = end.next;            }            if (end==null) break;            ListNode thisHead = prev.next;//记下要翻转链表的头节点            ListNode nextHead = end.next;//记下链表尾节点的next，方便后面链接链表            end.next = null;//断开链表            prev.next =  reverse(thisHead);//翻转，然后prev.next指向头节点            thisHead.next = nextHead;//翻转后头节点变为尾节点，通过.next把断开的链表重新链接            prev = thisHead;//prev和end设置为下次要翻转的链表头节点的上一个节点，类似dump            end = prev;        }        return dump.next;    }    //迭代法：一个一个反转    public ListNode reverse(ListNode head) {        ListNode prev = null;        ListNode curr = head;        while (curr != null) {            ListNode tmp = curr.next;   //记录当前节点的下一个节点            curr.next = prev;           //反转            prev = curr;                //prev和curr节点都前移一位            curr = tmp;        }        return prev;    //此时prev移动到了原链表的尾部，即反转后链表的首部，所以返回    }}

• 私有
• 公开
• 删除