算法-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) { LinkedList<ListNode> link = new LinkedList<ListNode>(); 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; } }