【LeetCode专辑 - 3】链表

链表是一种非常基础的数据结构，其中算法的题目难度一般都不是很大，重点在于画图理解、处理好边界条件和保留相关节点信息防止遍历后找不到所需节点

题目列表

删除链表的倒数第N个节点

先统计链表中有 $sum$ 个结点
找到倒数第 $n + 1$ 个节点
删除 $p->next = p->next->next$

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        // 记录链表一共有多少个节点
        int sum = 0;
        while (head != nullptr) {
            sum++;
            head = head->next;
        }
        // 找到倒数第 n + 1个节点
        auto p = dummy;
        for (int i = 0 ; i < sum - n; i++)
            p = p->next;
        p->next = p->next->next;
        return dummy->next;
    }
};

合并两个有序链表

双指针

关键在于定义虚拟头结点，防止返回结果找不到头结点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1; 
        // 定义虚拟头结点
        ListNode* dummy = new ListNode(-1);
        ListNode* tail = dummy;
        // 归并
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            }
            else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        if (l1 != nullptr) 
            tail->next = l1;
        if (l2 != nullptr)
            tail->next = l2;
        // 返回链表：不返回虚拟头结点
        return dummy->next;
    }
};

递归

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;

        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

两两交换链表中的节点

注意这里和反转链表的区别：两两交换相邻的节点
$p$ 每次指向要交换两个结点的前一个结点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        // 建立虚拟头结点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;
        while (p->next != nullptr && p->next->next != nullptr) {
            auto a = p->next;
            auto b = p->next->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy->next;
    }
};

删除排序链表中的重复元素

找到结点值相同的结点删除 $p->next = p->next->next$

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        auto p = head;
        while (p->next != nullptr) {
            if (p->val == p->next->val) {
                p->next = p->next->next;
            }
            else 
                p = p->next;
        }
        return head;
    }
};

相交链表

$headA$ 走到尾结点的时候，将指针指向 $headB$ 往前走； $headB$ 走到尾结点的时候，将指针指向 $headA$ 往前走
走到相交点的时候：走的总路程都是 $L1 + L2 + L$

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr)
            return nullptr;
        ListNode* pa = headA;
        ListNode* pb = headB;
        while (pa != pb) {
            if (pa == nullptr)
                pa = headB;
            else 
                pa = pa->next;
            if (pb == nullptr)
                pb = headA;
            else 
                pb = pb->next;
        }
        return pa;
    }
};

反转链表

迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr)
            return nullptr;
        ListNode* p = head;
        ListNode* q = head->next;
        while (q != nullptr) {
            ListNode* temp = q->next;
            // 改变指针走向
            q->next = p;
            // 顺次往后移动
            p = q;
            q = temp;
        }
        head->next = nullptr;
        return p;
    }
};

递归

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

回文链表

要使用 $O(1)$ 的空间来做：那么我们就不能遍历时候将节点值存储下来去判断
先统计链表中节点的个数 $n$
$half = n/2$ 向下取整是链表的一半（向下取整目的为了无需判断奇偶数的影响，跳 $n - half$ 步一定是后一半的头结点）
从头结点开始跳 $n - half$ 步找到后一半的头结点
将后半部分反转 $half - 1$ 次（反转链表操作）
双指针判断是否是回文链表
将后半部分链表恢复（否则过不了LeetCode评测）

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 记录链表一共有多少个结点
        int n = 0;
        auto p = head;
        while (p != nullptr) {
            p = p->next;
            n++;
        }
        if (n <= 1)
            return true;
        int half = n / 2;
        auto a = head;
        // 跳 n - half次到后面一半的头结点
        for (int i = 0; i < n - half; i++)
            a = a->next;
        auto b = a->next;
        // 翻转 half - 1 次
        for (int i = 0; i < half - 1; i++) {
            auto c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        // 双指针判断是否回文链表
        p = head;
        auto q = a;
        bool res = true;
        for (int i = 0; i < half; i++) {
            if (p->val != q->val) {
                res = false;
                break;
            }
            p = p->next;
            q = q->next;
        }
        // 将链表恢复：再次翻转 half - 1 次
        auto tail = a;
        b = a->next;
        for (int i = 0; i < half - 1; i++) {
            auto c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        tail->next = nullptr;

        return res;
    }
};

奇偶链表

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        auto odd = head, evenhead = head->next, even = evenhead;
        while (even != nullptr && even->next != nullptr) {
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenhead;
        return head;
    }
};

两数相加 II

class Solution {
public:
    /**
     * @brief 高精度加法
     * @param a 
     * @param b 
     * @return vector<int> 
     */
    static vector<int> add(vector<int>& a, vector<int>& b) {
        vector<int> c;
        int t = 0;
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            if (i < a.size())
                t += a[i];
            if (i < b.size())
                t += b[i];
            c.push_back(t % 10);
            t /= 10;
        }
        if (t > 0)
            c.push_back(1);
        return c;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> v1, v2, res;
        while (l1 != nullptr) {
            v1.push_back(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            v2.push_back(l2->val);
            l2 = l2->next;
        }
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        res = add(v1, v2);
        auto dummy = new ListNode(-1), p = dummy;
        for (int i = res.size() - 1; i >= 0; i--) {
            p->next = new ListNode(res[i]);
            p = p->next;
        }
        return dummy->next;
    }
};

分隔链表

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode*> res;
        int n = 0;
        auto p = root;
        while (p != nullptr) {
            n++;
            p = p->next;
        }
        int a = n / k;
        int b = n % k;
        p = root;
        // b个组元素是 a + 1个
        for (int i = 0; i < b; i++) {
            auto dummy = new ListNode(-1), q = dummy;
            for (int i = 0; i < a + 1; i++) {
                q->next = new ListNode(p->val);
                q = q->next;
                p = p->next;
            }
            res.push_back(dummy->next);
        }
        // k - b个组元素是 a 个
        for (int i = 0; i < k - b; i++) {
            auto dummy = new ListNode(-1), q = dummy;
            for (int i = 0; i < a; i++) {
                q->next = new ListNode(p->val);
                q = q->next;
                p = p->next;
            }
            res.push_back(dummy->next);
        } 
        while (res.size() < k) 
            res.push_back(nullptr);
        
        return res;
    }
};

【LeetCode专辑 - 3】链表

删除链表的倒数第N个节点

合并两个有序链表

双指针

递归

两两交换链表中的节点

删除排序链表中的重复元素

相交链表

反转链表

迭代

递归

回文链表

奇偶链表

两数相加 II

分隔链表

感谢您的支持，我会继续努力的!