博客

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的前面。

代码如下：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == NULL)
			return head;
		ListNode tmpHead(0);
		tmpHead.next = head;
		ListNode *p = &tmpHead;
		ListNode *q = p->next;
		while(q && q->val<x){
			p = p->next;
			q = p->next;
		}

		while (q != NULL)
		{
			ListNode * tmpNode = q->next;
			if(tmpNode == NULL)
			    break;
			if (tmpNode->val < x)
			{
				q->next = tmpNode->next;
				tmpNode->next = p->next;
				p->next = tmpNode;
				p = p->next;
			}else{
			    q = q->next;
			}
		}


		return tmpHead.next;
    }
};