一、题目
1、算法题目
“给定一个链表和特定值，对链表进行分割，使所有小于特定值的节点都出现在特定值节点之前。”
题目链接：
来源：力扣（LeetCode）
链接：86. 分隔链表 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个链表的头节点 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] 复制代码
二、解题
1、思路分析
这道题只需要两个链表，一个链表存放特定值前的节点，一个链表存放特定值后的界面，在遍历完成后，将两个链表链接即可。
具体实现就是，用两个链表分别指向当前链表的尾结点，然后从前往后遍历，根据当前节点是否大于特定值来讲这个节点放入到不同的链表中。
2、代码实现
代码参考：
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是链表的长度。
空间复杂度： O(1)
三、总结
对链表进行一次遍历，然后根据当前节点是否大于特定值来讲这个节点放入到特定链表下，最后合并链表。
