理解递归

反转链表

image.png

还是老样子，我们先假设n-1个链表已经反转完成了：

image.png

那么此时我们应该怎么做呢？此时1这个元素的next指针还是指向2的，因为后面的反转并不会影响1元素的next指针：

image.png

所以此时我们只需要将节点2的next设为1，将节点1的next设为null即可完成反转！

image.png

代码如下：
public ListNode ReverseList(ListNode head) {
// 这里得到n-1反转后链表的头节点，也就是反转前的最后一个节点
ListNode newHead = ReverseList(head.next);
// 将节点2的next设为节点1
head.next.next = head;
// 将节点1的next设为null
head.next = null;
return newHead;
}
  那么此时先一般就完成了，接下来就是寻找特殊（边界）情况了，一行行代码看下来发现head和head.next为null时会报异常，于是处理异常情况：  
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode newHead = ReverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}