java - 在类方法中递归地反转链表

Question

我的 SinglyLinkedList 类中有以下实例变量。

/* head is a reference to the front of the list (first element)
 * by default, head is initialized to null */
private Node head;

/* tail is a reference to the back of the list (last element)
 * by default, tail is initialized to null */
private Node tail; 

/* length is an integer that represents the size of our list,
 * by default it is assigned a value of 0 */
protected int length;

我想做的是编写一个名为 recursiveReverse() 的方法，它递归地反转 SinglyLinkedList 对象。如list.recursiveReverse()

我有一些想法，如果不传入 Node 对象，这些想法似乎不起作用

public SinglyLinkedList recursiveReverse() {
    static Node temp = head;
    if(temp == null) return null;
    if(length == 1) return this;

    Node temp_2 = temp.next;
    temp.next = null;
    // here is where i am stuck with the recursive call
    // is passing a Node as an argument the only way ?
    // if so, then how do I pass it in a class method ?
    // make the method static ?
 }

Answer 1

这应该适合你。

public ListNode reverseList(ListNode head) {
    if(head==null || head.next == null)
        return head;

    //get second node    
    ListNode second = head.next;
    //set first's next to be null
    head.next = null;

    ListNode rest = reverseList(second);
    second.next = head;

    return rest;
}

引用:Reverse a Singly Linked List.