LeetCode206 反转链表

发表于 | 分类于 |
字数统计: 117 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/reverse-linked-list/

题面

反转链表

解法

经典的链表题目，有迭代和递归两种解法

代码

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        while(head) {
            ListNode* cur = head -> next;
            head -> next = pre;
            pre = head;
            head = cur;
        }
        return pre;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return solve(head, nullptr);
    }
    ListNode* solve(ListNode* head, ListNode* prev) {
        if (head == nullptr) {
            return prev;
        }
        ListNode * nxt = head -> next;
        head -> next = prev;
        return solve(nxt, head);

    }
};