LeetCode 题解（159）: Partition List

本文主要是介绍LeetCode 题解（159）: 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.

题解：

Dummy头指针保证比x小，解决2->1, x = 2的问题。front指针记录第一个大于等于x的节点位置。挪动p, q指针。

C++版：

class Solution {
public:ListNode* partition(ListNode* head, int x) {if(head == NULL)return NULL;ListNode* dummy = new ListNode(x-1);dummy->next = head;ListNode* p = dummy;while(p->next && p->next->val < x)p = p->next;ListNode* q = p->next;ListNode* front = p->next;while(q) {if(q->next && q->next->val < x) {p->next = q->next;q->next = q->next->next;p->next->next = front;p = p->next;} else if(q->next && q->next->val >= x) {q = q->next;} elsebreak;}return dummy->next;}
};

Java版：

public class Solution {public ListNode partition(ListNode head, int x) {if(head == null)return null;ListNode dummy = new ListNode(x-1);dummy.next = head;ListNode p = dummy;while(p.next != null && p.next.val < x)p = p.next;ListNode q = p.next;ListNode front  = p.next;while(q != null) {if(q.next != null && q.next.val < x) {p.next = q.next;q.next = q.next.next;p.next.next = front;p = p.next;} else {q = q.next;}}return dummy.next;}
}

Python版：

class Solution:# @param {ListNode} head# @param {integer} x# @return {ListNode}def partition(self, head, x):if head == None:return Nonedummy = ListNode(x-1)dummy.next = headp = dummywhile p.next != None and p.next.val < x:p = p.nextq = p.nextstart = p.nextwhile q != None:if q.next != None and q.next.val < x:p.next = q.nextq.next = q.next.nextp.next.next = startp = p.nextelif q.next != None and q.next.val >= x:q = q.nextelse:breakhead = dummy.nextreturn head

这篇关于LeetCode 题解（159）: Partition List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---