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