题目：

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.

For example,

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

 

代码：oj测试通过 Runtime: 53 ms

1 # Definition for singly-linked list. 2 # class ListNode: 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.next = None 6  7 class Solution: 8     # @param head, a ListNode 9     # @param x, an integer10     # @return a ListNode11     def partition(self, head, x):12         if head is None or head.next is None:13             return head14         15         h1 = ListNode(0)16         dummyh1 = h117         h2 = ListNode(0)18         dummyh2 = h219         20         p = head21         while p is not None:22             if p.val < x :23                 h1.next = p24                 h1 = h1.next25             else:26                 h2.next = p27                 h2 = h2.next28             p = p.next29         30         h1.next = dummyh2.next31         h2.next = None

思路：

这道题的意思就是：把比x小的单拎出来，把大于等于x的单拎出来，再把两个Linked List首尾接起来。

技巧是设定两个虚拟表头dummyh1和dummyh2：保留住两个新表头。

另外需要设定两个迭代变量h1和h2：用于迭代变量