86. Partition List 分割链表

题目

给定一个链表头 head 和值 x，将这个链表分割，使得所有小于 x 的节点，都位于x节点的左侧。

image.png

解析

让所有节点值小于 x 的节点，都出现在该节点左侧，同时保证大于或等于这个节点的相对位置不改变。

1. 需要一个指针 tail，指向最后一个小于 x 的节点。
2. 还需要一个指针 p 用于遍历这个链表。
3. 需要一个指针 last，指向该节点的上一级，以便进行节点删除。
   具体做法就是，遍历链表，将小于 x 的节点移动到 tail 节点后。

伪代码

vhead.next = head
tail=vhead
for p != nil
  if p.val < x
    last.next = p.next
    p.next=tail.next
    tail.next = p
    tail = tmp
return vhead.next

伪代码逻辑没问题，但具体实施过程相当麻烦，首先 p 执政需要保留，不能在截断前后使用同一个变量，其次，last 指针和 tail 指针可能重叠，也需要单独判断，看起来不是一个简洁的做法。

看了解析，简单的方式是使用双链表，将小于 x 的数 append 到第一个链表，其他数 append 到第二个链表，最后将这两个链表合并即可。

代码

func partition(head *ListNode, x int) *ListNode {
    before := &ListNode{}
    after := &ListNode{}
    bh := before
    ah := after
    for head != nil {
        if head.Val < x {
            before.Next = head
            before = before.Next
        }else {
            after.Next = head
            after = after.Next
        }
        head=head.Next
    }
    after.Next = nil
    before.Next = ah.Next
    return bh.Next
}

image.png