反转链表

• https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan-v2&envId=top-100-liked

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

迭代

新建链表

两个指针，一个指向旧链表，一个指向新链表，不断从旧链表中复制节点，加到新链表头部。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * curr = nullptr;

        while(head!=nullptr){
            auto p = new ListNode(head->val);
            p->next = curr;
            curr = p;
            /*
            或者压缩成一行
            curr = new ListNode(head->val, curr);
            */
            head = head->next;
        }
        return curr;
    }
};

原地

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * curr = nullptr;

        while(head!=nullptr){
            // 记录旧链表当前节点
            auto p = head;
            // 旧链表指针后移
            head = head->next;
            // 将当前节点插入到新链表的头部
            p->next = curr;
            // 更新新链表的头部
            curr = p;
            /*
            或者另一种顺序：
            // 保存旧链表的下一个
            auto tmp = head->next;
            // 将节点加入新链表
            head->next = ans;
            ans = head;
            // 旧链表指针后移
            head = tmp;
            */
        }
        return curr;
    }
};

递归

递归比较难想。

要从后往前操作，不断的把后面节点的 next 指向当前节点。大致如下图：

n1 -> n2 -> n3 -> n4 -> nullptr

             head
            |
n1 -> n2 -> n3 <- n4
            |
            nullptr

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

        auto res = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }
};