递归反转列表

我们来反转整个链表

链表的定义如下

// 单链表节点的结构
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

我们的递归函数定义如下

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

我们随便写一个测试函数：

static ListNode reverse(ListNode head) {
    if (head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}


public static void main(String[] args) {
   ListNode listNode1 = new ListNode(1);
   ListNode listNode2 = new ListNode(2);
   ListNode listNode3 = new ListNode(3);
   ListNode listNode4 = new ListNode(4);
   listNode1.next = listNode2;
   listNode2.next = listNode3;
   listNode3.next = listNode4;
   ListNode result=reverse(listNode1);
   System.out.println(result);
}

对程序进行debug调试，可以看到我们的链表已经实现递归了

那么，如果理解呢？首先我们的链表定义如下

首先我们会执行reverse函数，这里我们会把head的下个节点，也就是下面所有的节点都传过去

ListNode last = reverse(head.next);