0086. Partition List

# 86. Partition List#

## 题目 #

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

``````
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

``````

## 解题思路 #

(以下描述定义，大于等于 x 的都属于比 x 大)

## 代码 #

``````
package leetcode

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/

// 解法一 单链表
func partition(head *ListNode, x int) *ListNode {
beforeHead := &ListNode{Val: 0, Next: nil}
afterHead := &ListNode{Val: 0, Next: nil}

before = before.Next
} else {
after = after.Next
}
}
after.Next = nil
}

// DoublyListNode define
type DoublyListNode struct {
Val  int
Prev *DoublyListNode
Next *DoublyListNode
}

// 解法二 双链表
func partition1(head *ListNode, x int) *ListNode {
}
for cur != nil {
if cur.Val < x {
tmp := &DoublyListNode{Val: cur.Val, Prev: nil, Next: nil}
compareNode := cur
for compareNode.Prev != nil {
if compareNode.Val >= x && compareNode.Prev.Val < x {
break
}
compareNode = compareNode.Prev
}
if compareNode.Val < x {
cur = cur.Next
continue
} else {
}
} else {
tmp.Next = compareNode
tmp.Prev = compareNode.Prev
compareNode.Prev.Next = tmp
compareNode.Prev = tmp
}
deleteNode := cur
if cur.Prev != nil {
deleteNode.Prev.Next = deleteNode.Next
}
if cur.Next != nil {
deleteNode.Next.Prev = deleteNode.Prev
}
}
cur = cur.Next
}
}

for cur != nil {
tmp := &DoublyListNode{Val: cur.Val, Prev: curDLN, Next: nil}
curDLN.Next = tmp
curDLN = tmp
cur = cur.Next
}
}

for cur != nil {
tmp := &ListNode{Val: cur.Val, Next: nil}
curLN.Next = tmp
curLN = tmp
cur = cur.Next
}