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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
题解：
链表分区，输入一个链表和一个整数x，将该链表所有节点值比x小的节点都在节点值大于等于x的节点前面，分区的链表节点依然按照原有的排列顺序。
如本题给出的事例，x=3，所以可以将原链表 1->4->3->2->5->2分为 1->2->2->NULL和4->3->5->NULL两部分；
按照这种思路，我们构造了两个初始节点，less_node和more_node；指向less_node节点地址的存储在less_head指针，该链表用于存储节点值小于x的节点；指向more_node节点地址的存储在more_head指针，该链表用于存储节点值大于等于x的节点；最后我们将已经移动到less_node尾节点的less_head指针的next指向more_node的第二个节点（因为头结点为0，没有实际用处），即：less_head->next = more_node.next；就可以得到分区连接后的节点less_node.next。 （注意C++代码中注释的部分）
My Solution（C/C++完整实现）：
#include <cstdio>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode * partition(ListNode *head, int x) {
ListNode less_node(0);
ListNode more_node(0);
ListNode *less_head = &less_node;
ListNode *more_head = &more_node;
while (head) {
if (head->val < x) {
less_head->next = head;
less_head = less_head->next;
}
else {
more_head->next = head;
more_head = more_head->next;
}
head = head->next;
}
more_head->next = NULL;
//注：由于此时的more_head = head;
//如果head后面的节点值都比x小，则全部都会连接到more_head后面;
//所以为了避免错误，我们令more_head->next = NULL;
less_head->next = more_node.next;
return less_node.next;
}
};
int main() {
ListNode a(1);
ListNode b(4);
ListNode c(3);
ListNode d(2);
ListNode e(5);
ListNode f(2);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
Solution s;
ListNode *result = s.partition(&a, 3);
while (result) {
printf("%d->", result->val);
result = result->next;
}
return 0;
}
结果：
1->2->2->4->3->5->
My Solution（Python）:
# 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
"""
temp_less = ListNode(0)
temp_more = ListNode(0)
less_head = temp_less
more_head = temp_more
while head:
if head.val < x:
temp_less.next = head
temp_less = temp_less.next
else:
temp_more.next = head
temp_more = temp_more.next
head = head.next
temp_less.next = more_head.next
temp_more.next = None
# 将链表尾节点next置空！
return less_head.next
