Leetcode-86Partition List

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