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

我不確定這是不是你想要的？ 是不需要的大小，

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（在需要管理，在代碼）

一個提示：

這將使用大小k該反轉的堆棧容易得多所需要的元素並且在其遞歸完整時彈出。

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)