随便整理的一些自用的leetcode题解

题目背景

LeetCode 86「分隔链表」。给定一个链表与目标值 x，要求重排链表，使所有小于 x 的节点出现在所有大于等于 x 的节点之前，且两段内部各自的相对顺序与原链表保持一致。

概念解释

稳定分隔：题目隐含要求”保持原相对顺序”，因此不能简单地交换值，需要按指针搬节点。
dummyNode（哨兵节点）：在头部加一个不存数据的节点，使得”插入到第一个小于 x 的位置之前”和”在中间插入”用同一段代码处理，避免单独写 head 改变的逻辑。
双指针法：用两个指针把链表逻辑地切成”已确认 < x 的前缀”和”待扫描区间”两段，扫描时按需把节点从后段搬到前段末尾。

实现原理

h1 指向”已确认 <x 的最后一个节点”（初始为 dummy），h2 沿着链表向后扫描：

h2->next->val >= x：跳过，h2 = h2->next；
h2->next->val < x：
- 若 h1 == h2，说明前缀还没断开，直接同时前进；
- 否则把 h2->next 这一节点从原位置摘下，插入到 h1->next 处，然后让 h1 前进一格而 h2 不动（因为它的 next 已经被重新接成了新链）。

扫描结束时返回 dummyNode->next 即可。整个过程只遍历一次链表，时间复杂度 O(n)，空间复杂度 O(1)。

参考实现

提示代码

/**
 * 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* partition(ListNode* head, int x) {

        ListNode* dummyNode = new ListNode(0);
        dummyNode->next = head;

        ListNode* h1 = dummyNode;
        ListNode* h2 = dummyNode;

        while(h2->next != nullptr)
        {
            if(h2->next->val >= x)
            {
                h2 = h2->next;
            }else
            {
                if(h1 == h2)
                {
                    h1 = h1->next;
                    h2 = h2->next;
                }
                else
                {
                    ListNode* t = h2->next;
                    h2->next = h2->next->next;
                    
                    t->next = h1->next;
                    h1->next = t;
                    h1 = h1->next;
                }
            }
        }

        return dummyNode->next;

    }
};

题解

思路

双指针法，并提前设置dummyNode，避免处理单节点情况。

h1指针用于指向所有小于X的节点，遇到小于X的节点，如果，h1==h2， h1，h2同时向后移动，否则，需要将h2的后继节点移动为h1的后继节点，同时h1前进1步，h2不动。 h2指针用于向后遍历，遇到大于等于X的节点，h2向后移动，

FEATURED TAGS

Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查速查内存 STL 调试性能分析性能读书笔记方法论架构网络 Timer mbedTLS TLS 安全负载均衡脚本工具 LRU 二叉树 BST 中序遍历回溯二分查找优先队列排序旋转数组 jenkins 部署

分隔链表题解

LeetCode 86 双指针解法

CATALOG