Leetcode题解剑指 Offer 06. 从尾到头打印链表

PROBLEM

难度简单

MY ANSWER

递归反转链表，然后从末尾往前遍历。时间复杂度O(n)，空间复杂度O(n)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reverseNext(ListNode* head) {
        if(!head->next) {
            return;
        }
        if(head->next->next) {
            reverseNext(head->next);
        }
        head->next->next = head;
    }
    vector<int> reversePrint(ListNode* head) {
        if(!head) {
            return {};
        }
        ListNode* tmp = head;
        while(tmp->next) {
            tmp = tmp->next;
        }
        reverseNext(head);
        head->next = NULL;
        vector<int> a;
        while(tmp->next) {
            a.push_back(tmp->val);
            tmp = tmp->next;
        }
        a.push_back(tmp->val);
        return a;
    }
};

BETTER SOLUTION

调用reverse、栈、递归push_back、迭代反转链表四种。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        //方法1：reverse反转法
        /*
        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        //使用algorithm算法中的reverse反转res
        reverse(res.begin(),res.end());
        return res;
        */

        //方法2：入栈法
        /*
        stack<int> s;
        //入栈
        while(head){
            s.push(head->val);
            head = head->next;
        }
        //出栈
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }
        return res;
        */

        //方法3：递归
        /*
        if(head == nullptr)
            return res;
        reversePrint(head->next);
        res.push_back(head->val);
        return res;
        */

        //方法4：改变链表结构
        ListNode *pre = nullptr;
        ListNode *next = head;
        ListNode *cur = head;
        while(cur){
            next = cur->next;//保存当前结点的下一个节点
            cur->next = pre;//当前结点指向前一个节点，反向改变指针
            pre = cur;//更新前一个节点
            cur = next;//更新当前结点
        }
        while(pre){//上一个while循环结束后，pre指向新的链表头
            res.push_back(pre->val);
            pre = pre->next;
        }
        return res;
    }
};

SUMMARY

FILO注意栈的使用，与递归有相似之处；可调用reverse反转数组。迭代和递归反转链表稍微改一下就能用于Leetcode 206. 反转链表、剑指 Offer 24. 反转链表、剑指 Offer II 024. 反转链表。

迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

递归

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