如何在O(n)时间内以某个给定大小的块反转单链表?

我最近遇到了一个算法问题:

以k块为单位反转单链表。 迭代方法是优选的。 关于k,结果列表的第一个块应该是最大的。 如果列表包含n个元素,则最后一个块将满或包含n mod k个元素。

For example: k = 2, list = [1,2,3,4,5,6,7,8,9], the reversed list is [8,9,6,7,4,5,2,3,1] k = 3, list = [1,2,3,4,5,6,7,8,9], the reversed list is [7,8,9,4,5,6,1,2,3] 

我的代码如下所示。

是否存在不使用堆栈或额外空间的O(n)算法?

 public static ListNode reverse(ListNode list, int k) { Stack stack = new Stack(); int listLen = getLen(list); int firstBlockSize = listLen % k; ListNode start = list; if (firstBlockSize != 0) { start = getBlock(stack, start, firstBlockSize); } int numBlock = (listLen) / k; for (int i = 0; i < numBlock; i++) { start = getBlock(stack, start, k); } ListNode dummy = new ListNode(0); ListNode cur = dummy; while (!stack.empty()) { cur.next = stack.peek(); cur = stack.pop(); while (cur.next != null) { cur = cur.next; } } return dummy.next; } public static ListNode getBlock(Stack stack, ListNode start, int blockSize) { ListNode end = start; while (blockSize > 1) { end = end.next; blockSize--; } ListNode temp = end.next; end.next = null; stack.push(start); return temp; } public static int getLen(ListNode list) { ListNode iter = list; int len = 0; while (iter != null) { len++; iter = iter.next; } return len; } 

这可以在O(n)时间内使用O(1)空间完成,如下所示:

  • 反转整个列表。
  • 反转各个块。

两者都可以使用非常类似于反转单个链表的标准方式来完成 ,整个过程类似于反转字符串中单词的排序 。

通过使用长度变量,可以非常容易地反转给定块。

当我们需要从一个块移动到另一个块时,复杂性就出现了。 我实现这一点的方法是让反向函数返回第一个和最后一个节点,并让最后一个节点指向我们原始链表中的下一个节点。 这是必要的,因为最后一个节点的下一个指针需要更新以指向我们下一个反向调用返回的第一个节点(我们不知道在该调用完成之前它需要指向什么)。

为简单起见,我在下面的代码中使用了一个null起始节点(否则我需要专门为起始节点提供服务,这会使代码变得复杂)。

 class Test { static class Node { Node next; T data; Node(T data) { this.data = data; } @Override public String toString() { return data.toString(); } } // reverses a linked-list starting at 'start', ending at min(end, len-th element) // returns {first element, last element} with (last element).next = (len+1)-th element static  Node[] reverse(Node start, int len) { Node current = start; Node prev = null; while (current != null && len > 0) { Node temp = current.next; current.next = prev; prev = current; current = temp; len--; } start.next = current; return new Node[]{prev, start}; } static  void reverseByBlock(Node start, int k) { // reverse the complete list start.next = reverse(start.next, Integer.MAX_VALUE)[0]; // reverse the individual blocks Node[] output; Node current = start; while (current.next != null) { output = reverse(current.next, k); current.next = output[0]; current = output[1]; } } public static void main(String[] args) { //Scanner scanner = new Scanner(System.in); Scanner scanner = new Scanner("3 9 1 2 3 4 5 6 7 8 9\n" + "2 9 1 2 3 4 5 6 7 8 9"); while (scanner.hasNextInt()) { int k = scanner.nextInt(); // read the linked-list from console Node start = new Node<>(null); Node current = start; int n = scanner.nextInt(); System.out.print("Input: "); for (int i = 1; i <= n; i++) { current.next = new Node<>(scanner.nextInt()); current = current.next; System.out.print(current.data + " "); } System.out.println("| k = " + k); // reverse the list reverseByBlock(start, k); // display the list System.out.print("Result: "); for (Node node = start.next; node != null; node = node.next) System.out.print(node + " "); System.out.println(); System.out.println(); } } } 

这输出:

 Input: 1 2 3 4 5 6 7 8 9 | k = 3 Result: 7 8 9 4 5 6 1 2 3 Input: 1 2 3 4 5 6 7 8 9 | k = 2 Result: 8 9 6 7 4 5 2 3 1 

现场演示 。

这是一种迭代的方式……你在这里阅读我的完整解释

 Node reverseListBlocks1(Node head, int k) { if (head == null || k <= 1) { return head; } Node newHead = head; boolean foundNewHead = false; // moves k nodes through list each loop iteration Node mover = head; // used for reversion list block Node prev = null; Node curr = head; Node next = null; Finish: while (curr != null) { // move the mover just after the block we are reversing for (int i = 0; i < k; i++) { // if there are no more reversals, finish if (mover == null) { break Finish; } mover = mover.next; } // reverse the block and connect its tail to the rest of // the list (at mover's position) prev = mover; while (curr != mover) { next = curr.next; curr.next = prev; prev = curr; curr = next; } // establish the new head, if we didn't yet if (!foundNewHead) { newHead = prev; foundNewHead = true; } // connects previous block's head to the rest of the list // move the head to the tail of the reversed block else { head.next = prev; for (int i = 0; i < k; i++) { head = head.next; } } } return newHead; }