java - 反转链表中的 K 个节点

Question

我已经实现了一个java代码，可以反转链表中的每个k节点，代码如下:

public class ReverseALinkedList {

    public static void main(String[] args) {
        int k = 2;
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        Node h = new Node(8);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;
        f.next = g;
        g.next = h;
        a.printLinkedList();
        Node head = reverseKLinkedList(a, k);
        head.printLinkedList();
    }

    private static Node reverseKLinkedList(Node first, int k) {
        Node current;
        Node temp;
        int count = 0;

        current = null;

        while (first != null && count < k) {
            temp = first.next;
            first.next = current;
            current = first;
            first = temp;
            ++count;
        }

        if (first != null) {
            first.next = reverseKLinkedList(first, k);
        }
        return current;
    }

    static class Node {
        public Node next;
        public int value;

        public Node(int value) {
            this.value = value;
        }

        public void printLinkedList() {
            Node head = this;
            while (head.next != null) {
                System.out.print(head.value + "->");
                head = head.next;
            }
            System.out.print(head.value + "->null");
            System.out.println();
        }

    }
}

当我使用以下链接列表执行代码时:

1->2->3->4->5->6->null 且 k 设置为 2，我得到的输出如下:

2->1->空

其余节点被反转(即 4->3、6->5)，但在递归调用期间不会返回它们。

有人可以告诉我如何解决这个问题吗？

Answer 1

另一种方法是迭代每个 K 节点并将其存储在 S 堆栈中。 其中，在每次 K 迭代中，每个 S 都存储在 N newList 中。

private static Node reverseKLinkedList(Node first, int k){
  Node newList, temp, current, walk, node;
  int count;

  node = first;
  newList = null;
  while(node != null) {
    count = 0;

    // stack the nodes to current until node is null or count is less than k
    current = null;
    while(node != null && count < k) {
      temp = current;
      current = new Node(node.value);
      current.next = temp;
      node = node.next;
      count++;
    }

    if(newList == null) // if newList is empty then assign the current node
      newList = current;
    else { 
      // else traverse against the newList until it reaches 
      // the last node and then append the current not
      walk = newList;
      while(walk.next != null) walk = walk.next;
      walk.next = current;
    }
  }

  return newList;

}