如何在O(n)时间内就地按给定的块大小反转单链表？

Question

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

将单链表以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<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;
}

- JoJo

---

这是一个O(n)算法。保持3个指针并在原地交换元素，记住旧的“下一个”。因此-反转A->B->C->D->E变成([]表示这里的指针) [A]->[B]->[C]->D->E(前三个元素的指针)，变成[A]<-[B] [C]->D->E此时我们停止指向A并开始指向D，所以A<-[B] [C]->[D]现在我们将C指向B，所以A<-[B]<-[C] [D]->E此时我们将指针从B移动到E(就像我们用A到D一样)，得到A<-B<-[C] [D]->[E]现在再次A<-B<-[C]<-[D] [E]，由于E是最后一个，我们将其作为头部并执行A<-B<-C<-D<-E，完成了。 - Benjamin Gruenbaum

Answer 1

这可以通过以下方式在O(n)时间内使用O(1)空间完成：

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

两者都可以使用与反转单向链表的标准方法非常相似的方法来完成，整个过程类似于反转字符串中单词的顺序。

仅反转给定块时，可以使用长度变量轻松完成。

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

为简单起见，在下面的代码中，我使用了一个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 

演示现场。

- Bernhard Barker

Answer 2

这里有一种迭代的方法来完成它... 你可以阅读我的完整解释。

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

- nem035

---

不，我认为你没有解决我的问题。你的输入是：1->2->3->4->5->6，你的输出是：2->1->4->3->6->5，并且k=2。但是我的输出是5->6->3->4->1->2。 - JoJo

Answer 3

这个部分包含多个单链表操作

import java.util.Scanner;
import java.util.Stack;

public class AddDigitPlusLL {

    Node head = null;
    int len =0;

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public void insertFirst(int data) {
        Node newNode = new Node(data);
        if (head != null)
            newNode.next = head;

        head = newNode;

    }

    public void insertLast(int data) {
        Node temp = head;
        Node newNode = new Node(data);
        if (temp == null)
            head = newNode;
        else {
            Node previousNode = null;
            while (temp != null) {
                previousNode = temp;
                temp = temp.next;
            }
            previousNode.next = newNode;
        }

    }

    public Long getAllElementValue() {
        Long val = 0l;
        Node temp=head;
        while(temp !=null) {
            if(val == 0)
                val=(long) temp.data;
            else
                val=val*10+temp.data;
            temp = temp.next;
        }

        System.out.println("value is :" +  val);
        return val;
    }

    public void print(String printType) {
        System.out.println("----------- :"+ printType +"----------- ");
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.data + "  --> ");
            temp = temp.next;
        }
    }

    public void generateList(Long val) {
        head = null;
        while(val > 0) {
            int remaining = (int) (val % 10);
            val = val/10;
            insertFirst(remaining);

        }
    }

    public void reverseList(Long val) {
        head =null;
        while(val >0) {
            int remaining = (int) (val % 10);
            val = val/10;
            insertLast(remaining);
        }
    }

    public void lengthRecursive(Node temp) {
        if(temp != null) {
            len++;
        lengthRecursive(temp.next);

        }
    }

    public void reverseUsingStack(Node temp) {
        Stack<Integer> stack = new Stack<Integer>();
        while(temp != null) {
            stack.push(temp.data);
            temp = temp.next;
        }

        head = null;
        while(!stack.isEmpty()) {
            int val = stack.peek();
            insertLast(val);
            stack.pop();
        }

        print(" Reverse Using Stack");
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s = new Scanner(System.in);
        AddDigitPlusLL sll = new AddDigitPlusLL();
        sll.insertFirst(5);
        sll.insertFirst(9);
        sll.insertLast(8);
        sll.print("List Iterate");
        Long val = sll.getAllElementValue();
        System.out.println("Enter the digit to add");
        Long finalVal = val +s.nextInt();
        s.close();
        sll.generateList(finalVal);
        sll.print("Add int with List Value");
        sll.reverseList(finalVal);
        sll.print("Reverse the List");
        sll.lengthRecursive(sll.head);
        System.out.println("Length with Recursive  :"+ sll.len);
        sll.print("Before call stack reverse method");
        sll.reverseUsingStack(sll.head);
    }
}

- TSK

Answer 4

反转单向链表的最简单方法如下。

private void reverse(Node node)
{
    Node current = Node;
    Node prev = null;
    Node next = null;

    if(node == null || node.next == null)
    {
        return node;
    }

    while(current != null)
    {
        next = current.next;
        //swap
        current.next = prev;
        prev = current;
        current = next;
    }
    node.next = current;
}

- Sumanth Varada