算法-k个一组翻转链表

题目给你链表的头节点head每k个节点一组进行翻转请你返回修改后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。示例 1输入head [1,2,3,4,5], k 2输出[2,1,4,3,5]题解思路一用双向链表解决该问题/** * 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) { LinkedListListNode link new LinkedListListNode(); ListNode cur head; int count 0; ListNode root new ListNode(); ListNode r root; while (cur ! null) { while (cur ! null count k) { ListNode temp cur.next; cur.next null; link.add(cur); cur temp; count; } while (link.size() 0) { ListNode node; if(count k){ node link.removeLast(); }else { node link.removeFirst(); } node.next r.next; r.next node; r node; } count 0; } return root.next; } }思路二用双向链表解决该问题需要使用o(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 groupHead new ListNode(); ListNode root groupHead; ListNode tail head; ListNode cur head; int count 0; while (cur ! null) { ListNode temp cur.next; cur.next groupHead.next; groupHead.next cur; cur temp; count; if (count k) { count 0; //回到尾节点 groupHead tail; //重新设置下一次的为节点 tail cur; } } if (count ! 0) { cur groupHead.next; groupHead.next null; while (cur ! null) { ListNode temp cur.next; cur.next groupHead.next; groupHead.next cur; cur temp; } } return root.next; } }