【题目】
Given a linked list and a value x,partition it such that all nodes less than x come before nodes greater than orequal to x.
You should preserve the original relativeorder 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.
给一个链表，可一个定值x，在保证链表顺序不变的前提下，将小于x的放在x前面，大于等于x的放其后。
【思路】
最简单的是创建两个头结点head1和head2；head1这条链表是小于x值的节点的链表，head2链表是大于等于x值的节点的链表，最后将head2链表链接到head链表的尾部即可。
【Python实现】
# -*- coding: utf-8 -*-
“””
Created on Wed Aug 9 16:41:48 2017
@author: Administrator
“””
# 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
“””
head1 = ListNode(0)#新的头结点，用于存放小于x的数
head2 = ListNode(0)#新的头结点，用于存放大于等于x的数
p1 = head1
p2 = head2
curr = head
while curr:
if curr.val < x:
p1.next = curr
curr = curr.next
p1 = p1.next
p1.next = None
else:
p2.next = curr
curr = curr.next
p2 = p2.next
p2.next = None
p1.next = head2.next
head = head1.next
curr = head
#打印新链表
while curr:
print(curr.val)
curr = curr.next
return head
if __name__ == ‘__main__’:
S= Solution()
l1 = ListNode(1)
l2 = ListNode(4)
l3= ListNode(3)
l4 = ListNode(2)
l5 = ListNode(5)
l6 = ListNode(2)
head = l1
l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l5
l5.next = l6
l6.next = None
S.partition(head,3)