204
[LeetCode]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的所有節點之前。
你應該保持在每兩個分區的節點的原始相對順序。
【分析】
無
【代碼】
/*********************************
* 日期：2014-01-28
* 作者：SJF0115
* 題目: 86.Partition List
* 網址：https://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;
}
};
最後更新：2017-04-03 12:54:51