k reverse связанный список

Question

Здесь я хочу рекурсивно отменить все элементы из связанного списка. Уточненный список 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

Я не уверен, что это все, что вы хотите? Размер не нужен,

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 2

На беглом взгляде вы не обновляете свою рекурсию, чтобы использовать newHead.

Кроме того, вам необходимо позаботиться о разрыве и создании указателей. Когда вы резервируете первые 3 элемента, они должны указывать на их предыдущий.

4.next = 3 и 5.next = 4 (Вы должны управлять, что в коде)

Один совет:

Это было бы гораздо проще, используя Stack размера к, что реверс требуемые элементы и всплывающие подсказки после его полной рекурсии.

Answer 3

1. Я не думаю, что вам нужен цикл в рекурсивной версии.

2. Чтобы сделать его универсальным, добавьте смещение.

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)