@TOC

AcWing 35. 反转链表

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。

样例

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

解法一：迭代

头插法。共三个关键结点，如图：

空间复杂度分析： 遍历时只有4个额外变量(dummy,tail,cur,nxt)，所以额外的空间复杂度是 $O(1)$。
时间复杂度分析： 只遍历一次链表，时间复杂度是 $O(n)$。

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) {
        //思路：不断让后面的结点连到dummy的后面，结点遍历完毕，也就反转完毕了
        if(head == null) return head;
        //由于用的是头插法，即后面的节点需要插在当前头节点之前，所以声明一个虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //表示本次要插入到dummy后的结点，即插入到原始链表的头节点位置
        ListNode cur = head.next;
        //tail指向一直不变，改变的是tail.next,用于将已经反转的部分链表和剩余还需要反转的链表相连
        ListNode tail = head;

        while(cur != null){
            //记住下一个需要头插的节点，避免等下cur.next改变指向，就找不到原来的cur.next了
            ListNode nxt = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            tail.next = nxt;//将已经反转的部分链表和剩余还需要反转的链表相连
            cur = nxt;//下一个要头插的节点
        }
        return dummy.next;
    }
}

解法二：递归

首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head.next)，这样我们可以将以head.next为头节点的链表翻转，并得到原链表的尾节点tail,它也是新链表的头节点，此时因为进行了反转，head.next是新链表的尾节点，我们令它的next指针指向head，并将head.next指向空即可将整个链表翻转，且新链表的头节点是tail。

空间复杂度分析： 总共递归 n 层，系统栈的空间复杂度是 $O(n)$，所以总共需要额外 $O(n)$ 的空间。
时间复杂度分析： 链表中每个节点只被遍历一次，所以时间复杂度是 $O(n)$。

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 tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}