# Partition List

## Question

### Problem Statement

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.

## 题解

### Python

"""
Definition of ListNode
class ListNode(object):

def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param x: an integer
@return: a ListNode
"""
return None

leftDummy = ListNode(0)
left = leftDummy
rightDummy = ListNode(0)
right = rightDummy
while node is not None:
if node.val < x:
left.next = node
left = left.next
else:
right.next = node
right = right.next
node = node.next
# post-processing
right.next = None
left.next = rightDummy.next

return leftDummy.next


### C++

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (head == NULL) return NULL;

ListNode *leftDummy = new ListNode(0);
ListNode *left = leftDummy;
ListNode *rightDummy = new ListNode(0);
ListNode *right = rightDummy;
while (node != NULL) {
if (node->val < x) {
left->next = node;
left = left->next;
} else {
right->next = node;
right = right->next;
}
node = node->next;
}
// post-processing
right->next = NULL;
left->next = rightDummy->next;

return leftDummy->next;
}
};


### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
ListNode leftDummy = new ListNode(0);
ListNode leftCurr = leftDummy;
ListNode rightDummy = new ListNode(0);
ListNode rightCurr = rightDummy;

while (runner != null) {
if (runner.val < x) {
leftCurr.next = runner;
leftCurr = leftCurr.next;
} else {
rightCurr.next = runner;
rightCurr = rightCurr.next;
}
runner = runner.next;
}

// cut off ListNode after rightCurr to avoid cylic
rightCurr.next = null;
leftCurr.next = rightDummy.next;

return leftDummy.next;
}
}


### 源码分析

1. 异常处理
2. 引入左右两个dummy节点及left和right左右尾指针
3. 遍历原链表
4. 处理右链表，置right->next为空(否则如果不为尾节点则会报错，处理链表时 以 null 为判断)，将右链表的头部链接到左链表尾指针的next，返回左链表的头部