2019/10/27 链表反转 （递归）

反转链表

反转链表为 leetcode 206题：

反转一个单链表。
示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：当最后一个节点或者最后一个节点的next节点为空时，开始反转，即让最后一个不为空的节点指向倒数第二个不为空的节点，并且把倒数第二个节点指向NULL，以此类推，直到第二个节点指向第一个节点，再把第一个节点指向NULL，即完成反转链表。

反转流程如下：

初始化链表.jpg
第一次反转.jpg
第二次反转.jpg
第三次反转.jpg
第四次反转.jpg

递归反转链表JAVA代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    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;

    }
}