leetcode 25 K 个一组反转链表
原题链接
问题
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
代码
/*** Definition for singly-linked list.* 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; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode h = new ListNode();// 返回的时候需要 h.next 这个h不会动他h.next = head; // 遍历需要一个新的头节点ListNode p = h;// 遍历一个节点i加1 如果 i%k==0 表明够了k个int i = 0;// 要翻转k个,ihead保留当前的头节点ListNode ihead = p;while(p.next != null){i++;p = p.next;if(i % k == 0){ //够了k个 翻转// ihead 是此次k个的头节点(额外的头节点,不在k个内)p是当前k个节点的尾节点(包含在k个内)// 返回值作为新的下一个k个的头节点 赋值给p和iheadp = reverseK(ihead,p);ihead = p;}}return h.next;}ListNode reverseK(ListNode head,ListNode tail){// q是k个节点的开始ListNode q = head.next;// 保留下第一个节点,它会变成此次的k个节点的最后一个,它的next要指向下一个k的第一个节点,他会作为下一轮的iheadListNode first = q;// 赋值为null,下面的过程和翻转整个链表类似head.next = null;while(q != null){// 头插法ListNode t = head.next;// 保留下一个节点ListNode p = q.next;head.next = q;q.next = t;// 此次的k个节点翻转完成,退出循环if(q == tail) {// 下一论的第一个节点拼接在此次最后一个节点的next上,不然链表就断了first.next = p;// 返回此次k的最后一个节点,做为下一轮的头节点iheadreturn first;};// 继续遍历q = p;}return null; }
}