java - 如何在 O(n) 时间内就地反转某个给定大小的 block 中的单链表？

Question

最近遇到一道算法题:

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

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;
}

Answer 1

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

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

两者都可以使用与 the standard way to reverse a singly linked-list 非常相似的东西来完成整个过程类似于reversing the ordering of words in a string .

使用长度变量可以很容易地只反转给定的 block 。

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

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

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 

Live demo .