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:
1
2
| Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
|
Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
h1 = l1 = ListNode(0)
h2 = l2 = ListNode(0)
while head:
if head.val < x:
l1.next = head
l1 = l1.next
else:
l2.next = head
l2 = l2.next
head = head.next
l2.next = None
l1.next = h2.next
return h1.next
|
