k 反转链表

Question

这里，我想递归地反转链表的每k个元素。对于链表 3 → 4 → 5 → 2 → 6 → 1 → 9 对于 kReverse(3) 变为 5 → 4→ 3→ 1→ 6→ 2→ 9→ 1 我收到 NullPointerException.

public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k, int size) {
        if(size<k) {
            return ReverseLinkedList.reverseLinkedList(head);
        }
        Node<Integer> temp = head;

        int i=1;
        while(i<k) {
            temp = temp.next;
            i++;
        }

        Node<Integer> newHead = temp;
        temp.next=null;

        ReverseLinkedList.reverseLinkedList(head);

        Node<Integer> smallerHead = kReverseLinkedList(head.next, k, size-k);

        head.next = smallerHead;

        return newHead;

    }

Answer 1

粗略地看一下，您没有更新递归来使用 newHead。

此外，你需要注意打破和制造指针。当您保留前 3 个元素时，它们需要指向它们的前一个。

4.next = 3 和 5.next = 4（您需要在代码中进行管理）

一个提示：

使用大小为 k 的 堆栈会容易得多，它会递归地反转所需的元素并在其满时弹出。

Answer 2

我不确定这是不是你想要的？不需要尺寸，

public class Node<T> {

    private T item;
    private Node<T> next;

    public Node(T item, Node<T> next) {
        this.item = item;
        this.next = next;
    }

    public Node(T item) {
        this.item = item;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public static Node<Integer> reverseLinkedList(Node<Integer> head) {
        if (head.next != null){
            Node<Integer> prev = head.next;
            Node<Integer> result = reverseLinkedList(prev);
            prev.next = head;
            return result;
        } else {
            return head;
        }
    }

    private static Node<Integer> kReverseLinkedList(Node<Integer> head, Node<Integer> cursor, int counter, int k) {
        Node<Integer> result;
        if (cursor.next == null){
            result = reverseLinkedList(head);
            head.next = null;
        } else if (counter > 0){
            result = kReverseLinkedList(head, cursor.next, counter-1, k);
        } else {
            Node<Integer> next = cursor.next;
            cursor.next = null;
            result = reverseLinkedList(head);
            head.next = kReverseLinkedList(next, next, k, k);
        }
        return result;
    }

    public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k) {
        Node<Integer> result = null;
        if (head != null){
            result = head;
            if (k > 1) {
                result = kReverseLinkedList(head, head, k-1, k-1);
            }
        }
        return result;
    }

    public static void print(Node<Integer> n) {
        if (n != null){
            System.out.print(n.item+" ");
            print(n.next);
        } else {
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[] data = {3,4,5,2,6,1,9};
        Node<Integer> head = new Node<>(data[0]);
        Node<Integer> tail = head;
        for (int i = 1; i < data.length; i++) {
            Node<Integer> n = new Node<>(data[i]);
            tail.setNext(n);
            tail = n;
        }
        print(head);
        head = kReverseLinkedList(head, 3);
        print(head);
    }
}

输出：

3 4 5 2 6 1 9 
5 4 3 1 6 2 9

Answer 3

我认为递归版本中不需要循环。
要使其通用，请添加一个偏移量。
不需要尺寸。

这里是带偏移量的真实递归版本（未测试）：

private static Node<Integer> tail;

public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k, int offset, Node<Integer> current) {
  if (offset > 1) {
    kReverseLinkedList(head.next, k, offset - 1, head.next);
    return head;
  } else if (offset == 1) {
    head.next = kReverseLinkedList(head.next, k, 0, head.next);
    return head;
  } else if (k == 1) {
    tail = current.next;
    return current;  
  } else {
    Node<Integer> n = kReverseLinkedList(head, k - 1, 0, current.next);
    current.next.next = current;
    if (current == head)
      head.next = tail;
    return n;
  }
}

// usage: kReverseLinkedList(myListHead, 8, 2, myListHead); (k >= 2, offset >= 0)

k 反转链表

k reverse a linked list

java

data-structures

linked-list

reverse