网络异常，图片无法展示
|
「这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战」
给你一个链表的头节点 head 和一个特定值 **x ，请你对链表进行分隔，使得所有 小于x 的节点都出现在 大于或等于x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
网络异常，图片无法展示
|
输入： head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] 复制代码
示例 2：
输入： head = [2,1], x = 2 输出：[1,2] 复制代码
提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
本题需要我们将链表根据给定值拆分两个分区，并且分区中的节点的相对位置应保留之前的相对位置
首先，当给定链表为空链表或者只有一个节点的时候，此时无法进行分隔，直接返回原链表即可
如果输入链表节点数量大于 1,则需要将输入链表中的节点按给定值 x 进行分区
最后将分区后存储大于等于 x 的节点的链表连接到存储小于 x 的链表的后边
最后返回结果链表即可
完成解题思路如下：
- 特殊判断链表为空或者只有一个节点，直接返回原链表
- 创建
smallHead虚拟头节点存储值小于x的节点组成的链表 - 创建
bigHead虚拟头节点存储值大于等于x的节点组成的链表 - 遍历输入两边，判断当前节点的值是否小于
x,如果成立，则将该节点连接到smallHead链表的末尾，反之连接到bigHead链表的末尾 - 将
bigHead链表末尾节点的next指针指向null，防止结果链表成环 - 将
bigHead链表连接到smallHead链表的末尾 - 返回
smallHead.next即可
整体过程如下：
网络异常，图片无法展示
|
代码如下：
var partition = function(head, x) { // 特判链表为空或者只有一个节点，直接返回 if(head === null || head.next === null) return head; // 创建虚拟头节点，存储小于X的节点组成的链表 const smallHead = new ListNode(0), // 创建虚拟头节点，存储不小于X的节点组成的链表 bigHead = new ListNode(0); let smallTail = smallHead, bigTail = bigHead, cur = head; // 遍历链表 while(cur){ // 如果该节点值小于X，将它连接到较小链表的末尾 if(cur.val<x){ smallTail.next = cur; smallTail = smallTail.next; }else{ // 反之连接到较大链表的末尾 bigTail.next = cur; bigTail = bigTail.next; } cur = cur.next; } // 将较大链表末尾节点 next 指向 null,防止结果链表成环 bigTail.next = null; // 将较大链表连接到较小链表的后面 smallTail.next = bigHead.next; // 返回较小链表虚拟头节点的 next return smallHead.next; }; 复制代码
至此我们就完成了 leetcode-86-分隔链表
如有任何问题或建议，欢迎留言讨论！
