[toc]

题目介绍

题目链接

https://leetcode-cn.com/problems/reverse-linked-list/description/
题目考点

链表，递归，迭代（用到了双指针），栈
题目难度

LeetCode-Easy
题目大意

给定1个链表，请将其反转
输入

链表的头结点
输出

反转后链表的头结点

题解一

解题思路

递归法

定义递归函数（函数功能是反转链表并返回链表反转后的头结点），将链表分成A（头结点）和B（头结点以外的其它结点）2部分，通过递归将链表B反转并得到其新的头结点，然后将A拼接在反转后链表B的尾部（注意链表B反转前其头结点正好是反转后的尾结点），最终返回新的链表（B）。
复杂度分析

假设链表有n个结点，则递归有n层，所以时间复杂度为$O(n)$，空间复杂度为$O(n)$。

代码

class Solution{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (nullptr == head || nullptr == head->next)
            return head;

        // devide the nodes into A(the original head) and B(the nodes except the original head).
        ListNode *ptrA = head; // A:原先的head
        ListNode *ptrB = reverseList(head->next); // B:将原先head以外的结点逆序并返回它的新head，此时head->next已经为链表B反转后的尾结点

        // 将A连接到B后面并将A的next设为空
        head->next->next = ptrA;
        ptrA->next = nullptr;

        // 返回反转后的链表
        return ptrB;
    }
};

题解二

解题思路

迭代法

本质就是头插法，需要用到双指针（1个遍历该链表，1个保存新链表的head），每取到1个结点就将其插入新链表的头部。
复杂度分析

假设链表有n个结点，则时间复杂度为$O(n)$、空间复杂度为$O(1)$。

代码

class Solution{
public:
    ListNode *reverseList(ListNode *head){
        ListNode *newHead = nullptr, *next;
        while (head != nullptr){
            // 保存下一个结点
            next = head->next;
            // 把当前结点插到头部
            head->next = newHead;
            // 更新头结点
            newHead = head;
            // 更新当前结点
            head = next;
        }
        return newHead;
    }
};

题解三

解题思路

栈法

遍历链表并将结点压入栈中，然后出栈建立新链表。
复杂度分析

假设链表有n个结点，则时间复杂度为$O(2n)$、空间复杂度为$O(n)$。

代码

class Solution{
public:
    ListNode *reverseList(ListNode *head){
        // 链表结点入栈（包括nullptr）
        stack<ListNode*> s;
        s.push(nullptr);
        for (auto p=head; p!=nullptr; p=p->next)
            s.push(p);
        // 取出新的头结点
        head = s.top();
        s.pop();
        // 将当前结点的next指向前一个结点（pre）
        ListNode *pre = head;
        while(!s.empty()){
            pre->next = s.top();
            s.pop();
            pre = pre->next;
        }
        return head;
    }
};

题解四

解题思路

原地反转法（三指针法）

定义3个指针pre、cur、next，以2个结点（pre和cur）为单位遍历各个结点。对于每个当前结点cur将其与pre的顺序逆置（cur->next=pre）再分别先后将pre和cur更新为cur和next。
复杂度分析

假设链表有n个结点，则时间复杂度为$O(n)$、空间复杂度为$O(1)$。

代码

class Solution{
public:
    ListNode *reverseList(ListNode *head){
        ListNode *pre=nullptr, *cur=head, *next;
        while(cur!=nullptr){
            // 保存next
            next = cur->next;
            // 逆序
            cur->next = pre;
            // 更新结点
            pre = cur;
            cur = next;
        }
        return pre; // cur为nullptr时，此时的pre是原链表的尾结点，也是链表反转后的头结点
    }
};

参考链接

作者：@臭咸鱼

转载请注明出处！

欢迎讨论和交流!