86. Partition List

发表于 | 分类于

每日一题 2019 - 04 - 17

题目：

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:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

解法：

这个题让把链表中比给定 x 大或者等于 x 的数据放在比 x 小的元素的后面，所以思路就很直观，使用一个vector 存放比 x 大的元素，使用一个 vector 存放比 x 小的元素，随后将前者推入后者之中，然后再将值挨个赋给原先的链表，即可完成任务，等于使用空间换时间效率；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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 == NULL )
        {
            return head ;
        }
        // 记录所有比x小的节点
        vector<int> first ;
        // 记录所有比x大于等于的节点
        vector<int> second ;
        ListNode * temp = head ;
        while( temp != NULL )
        {
            if(temp -> val < x)
            {
                first.push_back(temp -> val);
            }
            else
            {
                second.push_back(temp -> val);
            }
            temp = temp -> next ; 
        }
        for(int i = 0 ; i < second.size() ; i ++ )
        {
            first.push_back(second[i]);
        }
        temp = head ;
        for(int i = 0 ; i < first.size() ; i ++ )
        {
            temp -> val = first[i] ;
            temp = temp -> next ;
        }
        return head ;
    }
};
0%
undefined