LeetCode—分隔链表
给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例： 输入：head = 1->4->3->2->5->2, x = 3 输出：1->2->2->4->3->5 复制代码
来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/pa…
思路
首先根据题目判断题目的类别
那么我们在遍历的时候，如果只使用一个
哑结点可能是不能实现的重新理解题意是小于
x的元素节点都是在前面大于等于
x的元素节点都在后面那么根据上面梳理的思路就是创建两个
哑结点一个链保存小于
x的元素，另一个链保存大于等于x的元素最后将小于
x的元素指向大于等于x的元素明显就是普通遍历链表的思路
但是值得注意的是题目中提到的是要注意，原链表元素的相对顺序不能改变
class Solution { public ListNode partition(ListNode head, int x) { ListNode small = new ListNode(0); //创建哑节点 ListNode smallHead = small; ListNode large = new ListNode(0); //创建哑节点 ListNode largeHead = large; while(head != null){ if(head.val < x){ small.next = head; small = small.next; }else{ large.next = head; large = large.next; } head = head.next; } large.next = null; //将最后一个元素的下一个元素赋为空，"封死路口" small.next = largeHead.next; //将小值链表 与大值链表 连接; return smallHead.next; } }
作者：xiaoff
链接：https://juejin.cn/post/7016864384177668133