首页 > 代码库 > [LeetCode] Partition List

[LeetCode] 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.

思路:新建两个头结点,分别把小于x 的节点链接到第一个头结点后,把大于或等于x 的节点链接到第二个头节点后。

    时间复杂度O(n),空间复杂度O(1)

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *partition(ListNode *head, int x) {12         if(head == NULL) return head;13         14         ListNode *plow = new ListNode(-1);15         ListNode *plhead = plow;16         ListNode *phigh = new ListNode(-1);17         ListNode *phhead = phigh;18         ListNode *pt = head;19         20         while (pt != NULL) {21             if (pt->val < x) {22                 plow->next = pt;23                 plow = pt;24             } else {25                 phigh->next = pt;26                 phigh = pt;27             }28             pt = pt->next;29         }30         31         plow->next = phhead->next;32         phigh->next = NULL;33         34         return plhead->next;35     }36 };

 

[LeetCode] Partition List