题目：
给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
样例
给定链表 1->4->3->2->5->2->null，并且 x=3
返回 1->2->2->4->3->5->null
解题：
上面返回的结果好多不对的应该是： 1->2->2->3->4->5->null
想了好久不知道怎么搞，九章看到的程序，竟然搞两个链表链接起来。。。
Java程序：
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @param x: an integer
* @return: a ListNode
*/
public ListNode partition(ListNode head, int x) {
// write your code here
if(head == null) return null;
ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy, right = rightDummy; while (head != null) {
if (head.val < x) {
left.next = head;
left = head;
} else {
right.next = head;
right = head;
}
head = head.next;
} right.next = null;
left.next = rightDummy.next;
return leftDummy.next; } }
总耗时: 1573 ms
Python程序：
"""
Definition of ListNode
class ListNode(object): def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of linked list.
@param x: an integer
@return: a ListNode
"""
def partition(self, head, x):
# write your code here
if head == None:
return head
lefthead = ListNode(0)
righthead = ListNode(0)
left = lefthead
right = righthead
while head!=None:
if head.val<x:
left.next = head
left = left.next
else:
right.next = head
right = right.next
head = head.next
right.next = None
left.next = righthead.next
return lefthead.next
总耗时: 517 ms
和Java的有点小区别但是没有影响的。