[LeetCode-86] Partition List （链表数据分区）

72 阅读 0 评论 48 点赞

我是靠谱客的博主开心凉面，最近开发中收集的这篇文章主要介绍[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.

Subscribe to see which companies asked this question

【解题思路】

题意：
给定一个单链表和一个x，把链表中小于x的节点放到前面，
大于等于x的节点放到后面，每部分元素的原始相对位置不变。

思路：
其实很简单，遍历一遍链表，把小于x节点的都挂到small后，
把大于等于x的都放到big后面后，
最后再把大于等于的链表big挂到小于链表的后面就可以了。

【代码实现】

struct ListNode* partition(struct ListNode* head, int x) 
{
	/*1.异常处理*/
	if(!head || !head->next) 
		return head;

	struct ListNode *big = (struct ListNode *)malloc(sizeof(struct ListNode));
	struct ListNode *small = (struct ListNode *)malloc(sizeof(struct ListNode));
	struct ListNode *b = big;
	struct ListNode *s = small;

	b->next = NULL;
	s->next = NULL;
	
	struct ListNode *p = head;
	
	struct ListNode *pnext = NULL;
	while (head) {
		pnext = head->next; //保存节点非常重要
		/*大于x的节点挂在x的后面，即挂在b的后面即可*/
		if(head->val >= x) { 
			b->next = head;
			b = b->next;
			b->next = NULL;
		/*小于x的节点挂在x的后面，小的挂在s的后面即可*/
		} else {
			s->next = head;
			s = s->next;
			s->next = NULL;
		}
		
		head = pnext;
	}

	s->next = big->next;/*大的结点挂在小的节点后面*/

	head = small->next;/*小的头结点*/
	
	free(small);
	free(big);
	
	return head;
}