首页 > ACM题库 > LeetCode > LeetCode-Partition List[链表划分]
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.

题目来源:

题目大意:https://oj.leetcode.com/problems/partition-list/

给一个链表,将比x小的节点放在左边,比x大节点放在右边。需要保持原有的顺序。这类题目并不难,很适合作为面试的题目。

在IDE里可以容易的调试出来正确的代码,重要的怎么才能在面试时直接在纸上写出正确的代码。

这个算法的复杂度是比较确定的了,尽量用直观一点的算法,直接在原链表上操作比较麻烦,也容易出错。

可以设置两个链表,分别存储比x小的和比x大的。还有另一个技巧是,使用一个不存储数据的链表头,可以减少一些判断。

//============================================================================
// 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树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。