[LeetCode]86.Partition List

【题目】

Given a linked list and a valuex, partition it such that all nodes less thanxcome before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given1->4->3->2->5->2andx= 3,
return1->2->2->4->3->5.

【题意】

给定一个链表和一个值x，对它进行分区，使得小于x的所有节点来到大于或等于x的所有节点之前。
你应该保持在每两个分区的节点的原始相对顺序。

【分析】

无

【代码】

/*********************************
*   日期：2014-01-28
*   作者：SJF0115
*   题目: 86.Partition List
*   网址：http://oj.leetcode.com/problems/partition-list/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
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 *leftHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode *rightHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode *lpre = leftHead,*rpre = rightHead;
        while(head != NULL){
            if(head->val < x){
                lpre->next = head;
                lpre = head;
            }
            else{
                rpre->next = head;
                rpre = head;
            }
            head = head->next;
        }
        rpre->next = NULL;
        lpre->next = rightHead->next;
        return leftHead->next;
    }
};
int main() {
    Solution solution;
    int A[] = {1,3,2};
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *node;
    ListNode *pre = head;
    for(int i = 0;i < 3;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }
    head = solution.partition(head->next,5);
    while(head != NULL){
        printf("%d ",head->val);
        head = head->next;
    }
    return 0;
}

【温故】

/*-------------------------------------------------------------------
*   日期：2014-04-10
*   作者：SJF0115
*   题目: 86.Partition List
*   来源：https://leetcode.com/problems/partition-list/
*   结果：AC
*   来源：LeetCode
*   总结：
--------------------------------------------------------------------*/
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head == nullptr){
            return nullptr;
        }//if
        ListNode *left = new ListNode(-1);
        ListNode *right = new ListNode(-1);
        ListNode *p = left,*q = right,*cur = head;
        while(cur){
            if(cur->val < x){
                p->next = cur;
                p = cur;
            }//if
            else{
                q->next = cur;
                q = cur;
            }//else
            cur = cur->next;
        }//while
        q->next = NULL;
        p->next = right->next;
        return left->next;
    }
};