86. 分隔链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了86. 分隔链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

题目链接：
86. 分隔链表,# Leetcode,链表,数据结构

算法 = 双指针交替前行 & 题目特征 = 需要同时遍历两个链表，并且在遍历的过程中根据节点值的大小进行操作

参考题解：https://leetcode.cn/problems/partition-list/solutions/2362068/86-fen-ge-lian-biao-shuang-zhi-zhen-qing-hha7/
86. 分隔链表,# Leetcode,链表,数据结构
把原链表分为俩个链表，smlDummy 放小于 x 的元素, bigDummy 放大于 x 的元素。

他的解法是什么？

双指针交替而行。

他为什么用这个解法？

题目特征：链表一分为二。

具体实现用了俩个头节点。为什么使用头结点？文章来源地址https://www.toymoban.com/news/detail-733172.html

需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
比如，把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 新建两个链表
        ListNode *smlDummy = new ListNode(0), *bigDummy = new ListNode(0);
        // 遍历链表
        ListNode *sml = smlDummy, *big = bigDummy;
        while (head != nullptr) {
            // 将 < x 的节点加入 sml 节点后
            if (head->val < x) {
                sml->next = head;
                sml = sml->next;
            // 将 >= x 的节点加入 big 节点后
            } else {
                big->next = head;
                big = big->next;
            }
            head = head->next;
        }
        // 拼接两链表
        sml->next = bigDummy->next;
        big->next = nullptr;
        return smlDummy->next;
    }
};