题目描述

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

样例

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

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

算法1

(迭代)

1. 这道题可以不用dummy来实现
2. prev的初始化应该是nullptr，不能用new ListNode(-1)来动态初始化
3. 最后是return prev，因为最后cur指向了5的后面，是空，这时候prev指向的是5，又要反转，所以一直是输出它的前驱节点，所以输出prev。
4. 因为没有用dummy，所以cur == head，所以循环条件是while(cur)

时间复杂度

$O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;    // **1

        /*
        auto dummy = new ListNode(-1);
        dummy->next = head;
        */

        ListNode *prev = nullptr;
        auto cur = head;

        while(cur)
        {
            auto next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

算法2

(递归)

1. 这里不知道为什么，少写这句codeif(!head || !head->next) return head;会SE。
2. 最后是return tail，因为tail是5

时间复杂度

$O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // if(!head || !head->next) return NULL;    // **1
        if(!head || !head->next) return head;
        ListNode *tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;

        return tail;
    }
};