Leetcode206-反转链表

题目：见Leetcode206

解答：

方法一：添加dummy结点+头插法

if(head == NULL) return NULL;
        ListNode dummy = ListNode(INT_MIN);
        dummy.next = head;
        ListNode* post = head->next;
        while(post!=NULL)
        {
            head->next = post->next;
            post->next = dummy.next;
            dummy.next = post;
            post = head->next;
        }
        return dummy.next;

时间复杂度：n;空间复杂度：1//一个结点一个指针

8ms;-4.6%

优化：不需要dummy结点,逻辑有点绕，但一定要懂

ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* next = head;
        while(head!=NULL)
        {
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

时间复杂度：n;空间复杂度：1//两个指针

8ms;-4.6%

细节：

ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* next = head->next;
        while(head!=NULL)
        {
            head->next = pre;
            pre = head;
            head = next;
            next = head->next;
//这里可能存在head为空指针的状况，会报错！指针操作一定要先判空才能取next指针的结点!
        }
        return pre;
    }

方法二：不添加dummy结点的递归方法

ListNode* reverseList(ListNode* head) {
        //不用dummy结点的递归解法
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return node;
    }

时间复杂度：n；空间复杂度：n//递归栈

16ms;19.38%

总结

1.想要击败百分之百？为什么会缩短执行时间

static const auto __ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();