首页 > 代码库 > 【leetcode】Partition List

【leetcode】Partition List

2024-07-04 17:40:11   227人阅读

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的数，它的指针存放在before_p中，那么后面比x小的数都插入到它前面就可以了。在遍历的过程中，还要用指针front_p保存p的前一个指针，方便删除p所指向的节点。开始时候没有用这个指针，后来发现当删除的元素在链表结尾的时候，这个指针是必须的。

一种特殊的情况是需要头插的时候，比如

1. 给定的序列是2->1，给定的x是2，此时1要被头插到2前面去；

2. 给定的序列是2->3->1，x是3的时候1只需插入到2的后面，要注意这两种情况的区别。

利用判断before_p == head && before_p->val >= x，就可以甄别出要头插的情况了。因为在before_p == head时，有两种情况，一种是before_p指向的元素确实比x大或者相等，对应上述的第一种情况，需要头插；另外一种before_p指向的元素比x小，只需要把元素插入到before_p后面就可以了，对应于上述的第二种情况。

WA了一次才发现的，一般好难想到这一点>.<

代码：

 1 #include <iostream>
 2 #include <stdlib.h>
 3 using namespace std;
 4 
 5 struct ListNode {
 6      int val;
 7      ListNode *next;
 8      ListNode(int x) : val(x), next(NULL) {}
 9 };
10 
11 class Solution {
12 public:
13     ListNode *partition(ListNode *head, int x) {
14         ListNode* p = head;
15         ListNode* before_p = head;
16         ListNode* front_p;
17         
18         //找到链表中第一个大于等于x的数，以后比x小的数都插在它后面
19         while(p!= NULL && p->val < x){
20             before_p = p;
21             p = p->next;
22         }
23         
24         if(p !=NULL)
25         {
26             while(p != NULL){
27                 //找到一个比x小的数，要挪动它
28                 if(p->val < x){
29                     int value = http://www.mamicode.com/p->val;
30                     //删除比x的小的数的节点
31                     if(p->next != NULL)
32                     {
33                         ListNode* temp = p->next;
34                         p->val = temp->val;
35                         p->next = temp->next;
36                         free(temp);
37                     }
38                     else{
39                         front_p->next = NULL;
40                         ListNode* temp = p;
41                         p = NULL;
42                         free(temp);
43                     }
44                     //删除掉的节点插入到before_p后面
45                     ListNode* new_node= (struct ListNode*)malloc(sizeof(struct ListNode));
46                     new_node->val = value;
47 
48                     if(before_p == head && before_p->val >= x){//头插
49                         new_node->next = head;
50                         head = new_node;
51                         before_p = head;
52                     }
53                     else//不需要头插
54                     {
55                         new_node->next = before_p->next;
56                         before_p->next = new_node;
57                         before_p = new_node;
58                     }
59                 }
60                 else{
61                     front_p = p;
62                     p = p->next;
63                 }
64             }
65         }
66         return head;
67     }
68 };
69 
70 int main(){
71     struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
72     head->val = 2;
73     struct ListNode*next = (struct ListNode*)malloc(sizeof(struct ListNode));
74     next->val = 1;
75     head->next = next;
76     next->next = NULL;
77     /*struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
78     node3->val = 3;
79     next->next = node3;
80     struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
81     node4->val = 2;
82     node3->next = node4;
83     struct ListNode* node5 = (struct ListNode*)malloc(sizeof(struct ListNode));
84     node5->val = 5;
85     node4->next = node5;
86     struct ListNode* node6 = (struct ListNode*)malloc(sizeof(struct ListNode));
87     node6->val = 2;
88     node5->next = node6;
89     node6->next = NULL;*/
90 
91     Solution solution;
92     ListNode* h = solution.partition(head,2);
93     cout <<"dfs"<<endl;
94     while(h != NULL)
95     {
96         cout << h->val<<endl;
97         h = h ->next;
98     }
99 }

 

 

 


联系
我们