算法3.链表反转

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

解题思路

方法一：链表拼接

时间复杂度：$O(N)$

空间复杂度：$O(1)$

代码如下

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if(!head){return vector<int>(0); }
        else{
            vector<int> res;
            ListNode* reverse_res =reverse(head);
            while (reverse_res)
            {
                res.push_back(reverse_res->val);
                reverse_res = reverse_res->next;
            }
            // cout << res << endl;
            return res;
        }
    }
    ListNode* reverse(ListNode* head){
        if(!head->next)
            return head;
        else{
            ListNode* tmp=nullptr;
            ListNode* cur=head;
            ListNode* prev=nullptr;
            while(cur){
                tmp = cur->next;
                cur->next=prev;
                prev=cur;
                cur=tmp;
            }
            return prev;

        }
    }
};

解法分析

每次移动一个节点到新的指针中。

具体方法是：创建三个指针，一个是临时指针tmp，用来转移节点；一个指向原数组cur，用来在每次while循环定位接下来该转移的节点；一个是prev，存放反转后的链表。

解法注意点

• 注意理解三个指针交换过程的逻辑。

方法二：递归

时间复杂度：$O(N)$

空间复杂度：$O(N)$

代码如下

vector<int> res;
vector<int> reversePrint(ListNode* head) {
    if (!head) return res;
    reversePrint(head->next);
    res.push_back(head->val);
    return res;
    }

解法分析

每次传入 head->next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。回溯时用队列接着节点。