反转链表中的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，我得到如下输出:

零1 -> 2 ->

其余节点被反转(即，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;

}

Answer 2

当您反转第一个节点时，您将失去对下一个节点的引用，因此您将失去其余元素。为了实现这一点，你应该使用递归来存储节点或堆栈(这与递归基本相同)。

Proceed like this:
Store all the Nodes from the list in a stack.
For each node poped, the next elem is the top of the stack.
Repeat until no more nodes left.

Answer 3

下面是递归Java实现

public static <T> LinearNode<T> reverseAlternateKNodes(LinearNode<T> node, int k) {
    int count = 0;
    LinearNode<T> curr=node, prev = null, next = null;
    //reverse k nodes
    while (curr != null && count < k) {
        next = curr.next();
        curr.next(prev);
        prev = curr;
        curr = next;
        count ++;
    }
    // head should point to start of next k node
    node.next(curr);
    // skip nex knodes
    count = 0;
    while (curr != null && count < k- 1) {
        curr = curr.next();
        count ++;
    }
    // do it recursively
    if (curr != null) {         
        curr.next(reverseAlternateKNodes(curr.next(), k));
    }
    return prev;
}

这里是单元测试

@Test
public void reverseAlternateKNodes() {
    LinearNode<Integer> head = buildLinkedList(1,2,3,4,5,6,7,8,9,10);
    head = LinkedListUtil.reverseAlternateKNodes(head, 3);
    assertLinkedList(head, 3,2,1,4,5,6,9,8,7,10);
}

Answer 4

 public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while(curr!=null && count!=k){
        count++;
        curr = curr.next;
    }
    if(count==k){
        curr = reverseKGroup(curr,k);
        while(count-->0){
            ListNode temp = head.next;
            head.next = curr;
            curr = head;
            head = temp;
        }
        head = curr;
    }
    return head;
}