[leetcode] 86. Partition List

[leetcode] 86. Partition List

Description

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.

Example: Input:

head = 1->4->3->2->5->2, x = 3

Output:

1->2->2->4->3->5

分析

题目的意思是：给定一个链表，一个数x，要求比x小的放在链表前面，大于等于x的放在链表后面。

只需要遍历一遍就行了，slow指针指向要插向的位置，fast来寻找需要移动的结点。

代码

/** * 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) { if(!head) return head; ListNode* dummy=new ListNode(0); ListNode* slow=dummy; ListNode* fast=dummy; dummy->next=head; while(fast&&fast->next){ if(fast->next->val>=x){ fast=fast->next; }else{ if(fast==slow){ fast=fast->next; slow=slow->next; }else{ ListNode* temp=fast->next; fast->next=temp->next; temp->next=slow->next; slow->next=temp; slow=slow->next; } } } return dummy->next; }};

参考文献

​​[编程题]partition-list​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。