如何在O（n）时间内以某个给定大小的块反转单链表？ [英] How to reverse a singly-linked list in blocks of some given size in O(n) time in place?

问题描述

我最近遇到了算法问题：

I recently encounter an algorithm problem:

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

Reverse a singly-linked list in blocks of k in place. An iterative approach is preferred. The first block of the resulting list should be maximal with regards to k. If the list contains n elements, the last block will either be full or contain n mod k elements.

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）算法？

Is there an O(n) algorithm that doesn't use a stack or extra space?

public static ListNode reverse(ListNode list, int k) {
    Stack<ListNode> stack = new Stack<ListNode>();
    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<ListNode> 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）空格的时间如下：

This can be done in O(n) time using O(1) space as follows:

• 反转整个清单。


• 反转各个区块。

两者都可以使用与反转单链表的标准方法，整个过程类似颠倒字符串中单词的排序。

Both can be done using something very similar to the standard way to reverse a singly linked-list and the overall process resembles reversing the ordering of words in a string.

仅反转a通过使用长度变量可以很容易地完成给定块。

Reversing only a given block is fairly easily done by using a length variable.

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

The complication comes in when we need to move from one block to the next. The way I achieved this was by having the reverse function return both the first and last nodes and having the last node point to the next node in our original linked-list. This is necessary because the last node's next pointer needs to be updated to point to the first node our next reverse call returns (we don't know what it will need to point to before that call completes).

为简单起见，我在下面的代码中使用了一个 null start节点（否则我需要专门为起始节点提供服务，这将使代码复杂化。

For simplicity's sake, I used a null start node in the code below (otherwise I would've needed to cater for the start node specifically, which would've complicated the code).

class Test
{
   static class Node<T>
   {
      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 <T> Node<T>[] reverse(Node<T> start, int len)
   {
      Node<T> current = start;
      Node<T> prev = null;
      while (current != null && len > 0)
      {
         Node<T> temp = current.next;
         current.next = prev;
         prev = current;
         current = temp;
         len--;
      }
      start.next = current;
      return new Node[]{prev, start};
   }

   static <T> void reverseByBlock(Node<T> start, int k)
   {
      // reverse the complete list
      start.next = reverse(start.next, Integer.MAX_VALUE)[0];
      // reverse the individual blocks
      Node<T>[] output;
      Node<T> 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<Integer> start = new Node<>(null);
         Node<Integer> 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<Integer> 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 

现场演示。

这篇关于如何在O（n）时间内以某个给定大小的块反转单链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！