算法13.反转链表

题目描述

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

示例 1：

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

解题思路

方法一：普通分析

时间复杂度：$O(N)$

空间复杂度：$O(1)$

代码如下

//摘自LeetCode中Krahets大佬
class Solution:
    def isNumber(self, s: str) -> bool:
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in "eE": t = 'e'     # e or E
            elif c in ". ": t = c       # dot, blank
            else: t = '?'               # unknown
            if t not in states[p]: return False
            p = states[p][t]
        return p in (2, 3, 7, 8)

方法二：递归分析

时间复杂度：$O(N)$

空间复杂度：$O(1)$

代码如下

//摘自LeetCode中huwt大佬
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

解法分析

之前有一道类似的反转题，但这道题主要是递归用的太妙了，记录一下！

递归是尾递归，即在返回的时候做反转操作，具体过程如下：

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 $ret$ .
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的 $next$ 指针指向当前节点。
• 同时让当前结点的 $next$ 指针指向 $NULL$ ，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成。