剑指 Offer 24. 反转链表

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

❤双指针

思路

算法

实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

复杂度分析

• 时间复杂度:
• 空间复杂度:

❤❤递归

思路

• 一直递归到链表的最后一个节点，该节点就是反转后的头结点，记作ret。
• 此后，在返回时 ，让当前节点的下一节点指向当前节点，同时让当前节点的next指向NULL，从而实现翻转。
• 当递归函数全部出栈后，链表翻转完成。

实现

//骚操作递归！
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;
    }
//正规操作递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL) return head;
        dfs(head,head->next);
        return ans;
    }
private:
    ListNode* ans=NULL;
    void dfs(ListNode* pre ,ListNode* cur){
        if(cur==NULL){
            ans=pre;
            return;
        }
        dfs(pre->next,cur->next);
        cur->next=pre;
        pre->next=NULL;
    }
};

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分