6

如果给你一个链表的头部，并被要求反转每 k 个节点序列，那么在 Java 中如何做到这一点？例如，a->b->c->d->e->f->g->hk = 3 将是c->b->a->f->e->d->h->g->f

任何一般帮助甚至伪代码都将不胜感激！谢谢！

4

6 回答 6

4

如果k期望相当小，我会选择最简单的事情：完全忽略它是一个链表的事实，并将每个子序列视为一个数组类型的事物来反转。

因此，如果您的链表的节点类是 a Node<T>，则创建 aNode<?>[]的 size k。对于每个段，加载k Nodes到数组列表中，然后用一个简单的for循环来反转它们的元素。在伪代码中：

// reverse the elements within the k nodes
for i from 0 to k/2:
    nodeI = segment[i]
    nodeE = segment[segment.length-i-1]
    tmp = nodeI.elem
    nodeI.elem = nodeE.elem
    nodeE.elem = tmp

优点：非常简单，O(N) 性能，利用易于识别的反转算法。

缺点：需要一个k-sized 数组（只需一次，因为您可以在每个段中重复使用它）

另请注意，这意味着每个Node都不会在列表中移动，只会在Node持有的对象中移动。这意味着每个Node人最终都会持有与以前不同的物品。这可能好也可能不好，这取决于您的需要。

于 2012-04-22T21:45:10.093 回答
1

时间 O(n); 空间 O(1)

列表反转的一个通常要求是您在 O(n) 时间和 O(1) 空间内进行。这消除了递归或堆栈或临时数组（如果 K==n 怎么办？）等。因此，这里的挑战是修改就地反转算法以解决该K因素。而不是K我dist用于距离。

这是一个简单的原地反转算法： 使用三个指针在原地遍历链表：b指向新链表的头部；c指向未处理列表的移动头；以方便和a之间的交换。bc

 A->B->C->D->E->F->G->H->I->J->L //original
 A<-B<-C<-D    E->F->G->H->I->J->L //during processing
          ^    ^
          |    |
          b    c
 `a` is the variable that allow us to move `b` and `c` without losing either of
  the lists.

Node simpleReverse(Node n){//n is head
if(null == n || null == n.next)
   return n;
Node a=n, b=a.next, c=b.next;
a.next=null; b.next=a;
while(null != c){
   a=c;
   c=c.next;
   a.next=b;
   b=a;
}
return b;
}

要将simpleReverse算法转换为chunkReverse算法，请执行以下操作：

1]反转第一个块后，设置head为b; head是结果列表的永久负责人。

2] 对于所有其他块，设置tail.next为b; 回想一下，这b是刚刚处理的块的头部。

其他一些细节：

3] 如果列表有一个或更少的节点或dist为1或更少，则返回列表而不进行处理。

4]使用计数器cnt来跟踪dist连续节点何时被反转。

5]使用变量tail来跟踪刚刚处理的块tmp的尾部，并跟踪正在处理的块的尾部。

6] 请注意，在处理一个块之前，它的头，必然成为它的尾巴，是你遇到的第一个节点：所以，将它设置为tmp，这是一个临时的尾巴。

public Node reverse(Node n, int dist) {
  if(dist<=1 || null == n || null == n.right) 
      return n;
  Node tail=n, head=null, tmp=null;
  while(true) {
      Node a=n, b=a.right; n=b.right;
      a.right=null; b.right=a;
      int cnt=2;
      while(null != n && cnt < dist) {
          a=n; n=n.right; a.right=b; b=a;
          cnt++;
      }
      if(null == head) head = b;
      else {
          tail.right=b;tail=tmp;
      }
      tmp=n;
      if(null == n) return head;
      if(null == n.right) {
          tail.right=n;
          return head;
      }
  }//true
  }
于 2012-04-22T23:27:51.433 回答
1

这是相当高级的，但我认为它会提供一些指导。

我有一个像void swap3(Node first, Node last)这样的辅助方法，在列表的任意位置取三个元素并将它们反转。这应该不难，并且可以递归地完成（交换外部元素，递归内部元素，直到列表的大小为 0 或 1）。现在我想到了，swapK()如果您使用递归，您可以轻松地将其概括为。

一旦完成，你就可以沿着你的链表走并调用swapK()每个k节点。如果列表的大小不能被 整除k，您可以不交换最后一位，或者length%k使用交换技术反转最后一个节点。

于 2012-04-22T21:33:48.570 回答
1

例如通过 Common Lisp

(defun rev-k (k sq)
  (if (<= (length sq) k)
      (reverse sq)
      (concatenate 'list (reverse (subseq sq 0 k)) (rev-k k (subseq sq k)))))

其他方式例如通过 F# 使用 Stack

open System.Collections.Generic
let rev_k k (list:'T list)  =
  seq {
    let stack = new Stack<'T>()
    for x in list do
      stack.Push(x)
      if stack.Count = k then
        while stack.Count > 0 do
          yield stack.Pop()
    while stack.Count > 0 do
      yield stack.Pop()
  }
  |> Seq.toList
于 2012-04-22T23:39:47.480 回答
0

此实现使用 ListIterator 类：

LinkedList<T> list;
//Inside the method after the method's parameters check
ListIterator<T> it = (ListIterator<T>) list.iterator(); 
ListIterator<T> reverseIt =  (ListIterator<T>) list.listIterator(k); 

for(int i = 0; i< (int) k/2; i++ )
{
    T element  = it.next();
    it.set(reverseIt.previous());
    reverseIt.set(element);
}
于 2012-04-23T15:08:34.603 回答
0

使用堆栈并递归地从列表中删除 k 个项目，将它们推送到堆栈然后弹出它们并将它们添加到位。不确定这是否是最好的解决方案，但堆栈提供了一种反转事物的正确方法。请注意，如果您有队列而不是列表，这也有效。只需将 k 个项目出列，将它们推入堆栈，将它们从堆栈中弹出并将它们入队 :)

于 2012-04-23T03:38:17.390 回答