分隔链表

#双指针

题目描述

给你一个链表的头节点 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

思路

• 利用 虚拟结点、双指针技巧，遍历head，给p1，p2赋值。p.Next为了断开与原链表的关联。最后再把p1，p2首位相连。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
   d1:=&ListNode{-1,nil}
   d2:=&ListNode{-1,nil}

   p,p1,p2:=head,d1,d2

   for p!=nil{
       if p.Val<x{
           p1.Next=p
           p1=p1.Next
       }else{
           p2.Next=p
           p2=p2.Next
       }

       temp:=p.Next
       p.Next=nil
       p=temp
   }

   p1.Next=d2.Next
   return d1.Next
}