反转链表

反转链表

一、题目

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

进阶：部分链表反转。给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

Leetcode：https://leetcode.cn/problems/reverse-linked-list-ii/

二、思路

需要三个指针，一个 perv、一个 cur、一个 next 三个指针。每次先使用 next 保存 cur->next，然后将 cur->next 指向 prev，接下来分别给 prev 赋上 cur，cur 则赋上 next。完成一次指针的反转，依次遍历即可。

那么对于部分链表的反转。而且要求一趟扫描完成反转。我们相当于是头插法完成，即在要反转的部分链表中，每次将后面的元素头插到反转部分的起始位置。注意使用一个傀儡节点有利于问题的解决

三、code

#include <iostream>
#include <vector>

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    explicit ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

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

// 反转部分链表
class Solution2 {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (head == nullptr) {
            return head;
        }
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* prev = dummy;
        for (int i = 0; i < left-1; i++) {
            prev = prev->next;
        }
        ListNode* curr = prev->next;
        ListNode* next = nullptr;
        for (int i = 0; i < right-left; i++) {
            next = curr->next;
            curr->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

void print_list(ListNode* node) {
    for (; node != nullptr; node = node->next) {
        std::cout << node->val << " ";
    }
    std::cout << std::endl;
}

ListNode* gen_list(const std::vector<int> vec) {
    ListNode* root = new ListNode(vec[0]);
    ListNode* tmp = root;
    for (size_t i = 1; i < vec.size(); ++i) {
        tmp->next = new ListNode(vec[i]);
        tmp = tmp->next;
    }
    return root;
}

int main() {
    ListNode* root = gen_list({1, 2, 3, 4, 5, 6, 7});
    print_list(root);
    Solution s;
    ListNode* res = s.reverseList(root);
    print_list(res);
    return 0;
}