题目：

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.

链接： 

题解：

创建两个新链表，每次当前节点值比x小的放入headA，其余放入headB，最后把两个链表接起来。 要注意把右侧链表的下一节点设置为null。

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {    public ListNode partition(ListNode head, int x) {        if(head == null || head.next == null)            return head;        ListNode headLeft = new ListNode(-1);        ListNode headRight = new ListNode(-1);        ListNode nodeLeft = headLeft;        ListNode nodeRight = headRight;                while(head != null){            if(head.val < x){                nodeLeft.next = head;                nodeLeft = nodeLeft.next;            } else {                nodeRight.next = head;                nodeRight = nodeRight.next;            }                            head = head.next;        }                nodeRight.next = null;        nodeLeft.next = headRight.next;        return headLeft.next;    }}

 

Update: 昨晚前面两道难题，终于有简单题换换口味了...好高兴 -_____-!!

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode partition(ListNode head, int x) {        if(head == null || head.next == null)            return head;        ListNode dummyLeft = new ListNode(-1);        ListNode dummyRight = new ListNode(-1);        ListNode left = dummyLeft;        ListNode right = dummyRight;                while(head != null) {            if(head.val < x) {                left.next = head;                left = left.next;            } else {                right.next = head;                right = right.next;            }            head = head.next;        }                right.next = null;        left.next = dummyRight.next;                return dummyLeft.next;    }}

 

二刷：

这道题比较简单，创建两个fakeHead，以及两个runner，直接one pass过就可以了

Java:

Time Complexity - O(n)， Space Complexity - O(1)

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode partition(ListNode head, int x) {        if (head == null || head.next == null) {            return head;        }        ListNode leftHead = new ListNode(-1), rightHead = new ListNode (-1);        ListNode left = leftHead, right = rightHead;        while (head != null) {            if (head.val < x) {                left.next = head;                left = left.next;            } else {                right.next = head;                right = right.next;            }            head = head.next;        }        right.next = null;        left.next = rightHead.next;        return leftHead.next;    }}

 

 

三刷:

创建两个表头，三个runner，然后遍历时node的值跟x进行比较，最后再merge就可以了。

Java:

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode partition(ListNode head, int x) {        ListNode leftHead = new ListNode(-1);        ListNode rightHead = new ListNode(-1);        ListNode node = head, left = leftHead, right = rightHead;        while (node != null) {            if (node.val < x) {                left.next = node;                left = left.next;            } else {                right.next = node;                right = right.next;            }            node = node.next;        }        right.next = null;        left.next = rightHead.next;        return leftHead.next;    }}

 

 

测试：

Reference:  http://www.cnblogs.com/springfor/p/3862392.html