[Day13]] 2022-03-10 86. 分隔链表

/**
* 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
}