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。之前偷懒没有处理这个元素,但是题意要求保持原顺序。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *partition(ListNode *head, int x) { ListNode *gard = new ListNode(0); ListNode *par = new ListNode(x); ListNode *pp = par; gard->next = head; ListNode *pre = gard; ListNode *temp = head; if(head == NULL) return head; while(temp -> next != NULL) { if(temp -> val >=x) { pre -> next = temp ->next; temp ->next = NULL; pp->next = temp; pp = pp->next; temp =pre->next; } else { pre =pre->next; temp = temp->next; } } if(temp -> val >=x) { pp->next = temp; pre->next = NULL; temp =pre; } temp ->next = par ->next; return gard->next; } };