86. 分隔链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func partition(head *ListNode, x int) *ListNode {
  9.     // 遍历链表将所有小于x的节点摘下, 连接成为一个新的链表 
  10.     // 再将两个链表连接起来
  11.     var preHead = new(ListNode)
  12.     preHead.Next = head
  13.     var List = new(ListNode)
  15.     pre := preHead
  16.     p := preHead.Next
  18.     cur := List
  20.     for p != nil {
  21.         if p.Val < x {
  22.             node := p
  23.             p = p.Next
  24.             pre.Next = p
  26.             node.Next = cur.Next
  27.             cur.Next = node
  28.             cur = cur.Next
  29.         } else {
  30.             pre = pre.Next
  31.             p = p.Next
  32.         }
  33.     }
  35.     cur.Next = preHead.Next
  36.     return List.Next
  37. }