2014
07-09

# LeetCode-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.

//============================================================================
// Name        : 链表.cpp
// Author      : Coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : LeetCode-Partition List
//============================================================================

#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 * small = new ListNode(0); //小于x的链表头(不存储数据)
ListNode * large = new ListNode(0); //大于等于x的链表头(不存储数据)
ListNode * lastSmall = small,* lastLarge = large;
ListNode * cur = head;
while(cur){
if(cur->val < x){
lastSmall->next = cur;
lastSmall =  lastSmall->next;
}else{
lastLarge->next = cur;
lastLarge =  lastLarge->next;
}
cur = cur->next;
lastSmall->next = lastLarge->next = NULL; //需要将最后的一个节点指向空
}
lastSmall->next = large->next;
return small->next;
}
};
int main() {
ListNode * head = new ListNode(1);
head->next = new ListNode(4);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(2);
head->next->next->next->next->next->next = new ListNode(6);

Solution s;
ListNode * h = s.partition(head, 3);

//测试
while(h){
cout << h->val << " ";
h = h->next;
}
cout << endl;
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。