前言
链表的特点 适合 插入和 删除 一个元素，不需要整体移动。
go代码
代码语言：javascript复制/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔
你应当 保留 两个分区中每个节点的初始相对位置。
*/
func partition(head *ListNode, x int) *ListNode {
//01 合法性检查
if nil == head || nil == head.Next {
return head
}
//02 固定头节点插入
//case1 x=1 input=【1,2,3,4,5】 都比1大，位置保持不变。
//case2 x=5 input=【1,2,3,4,5】 都比5小，位置保持不变。
//case3 X =5 INPUT=【6,5,4,3,2,1】 都比5小,需要翻转。
//比x小有2个情况，需要翻转（这里需要固定头节点），不需要翻转。
dummnyhead := ListNode{
Val: -1,
Next: head,
}
//03 定义三路指针
ptail := &dummnyhead //排序后小于元素x的最后一个位置。
pcur := head
ppre := ptail
//04 链表的遍历
for pcur != nil {
if pcur.Val >= x {
//case1 x=1 input=【1,2,3,4,5】 都比1大，位置保持不变。
ppre = pcur
pcur = pcur.Next
} else if ptail.Next == pcur {
//case2 x=5 input=【1,2,3,4,5】 都比5小，位置保持不变。
ptail = pcur
ppre = pcur
pcur = pcur.Next
//对同一个位置 不需要翻转
} else {
//一个元素把链表 分割成为2部分，全部大于 x，全部小于 x case1 和case2 是理想情况
//case3 X =5 INPUT=【6,5,4,3,2,1】 都比5小,需要翻转。
ppre.Next = pcur.Next //删除
pcur.Next = ptail.Next //链表尾节点插入
ptail.Next = pcur //链表尾节点插入
ptail = pcur // 小于x的最后一个位置。
pcur = ppre.Next //
}
}
return dummnyhead.Next
}
