leetcode 148 排序链表

有点难的题目,因为没有想到归并排序的思想。简单来说就是不断的对半分割,然后递归的完成两个分块的排序之后,再将这两个排好序的分块按序合并,就完成了排序。先贴一种自顶向下的方法。这种方法的细节之处在于不断的分割过程中,对只剩两个元素的情况进行处理,删去第二个元素,也就是将头结点的next指针设为null。而这种方法的依据在于分割的过程中存在重复的元素,比如3个元素的单元会被分为两个2元素的单元,第一个单元继承原始单元的第一个元素,第二个则继承第二个,第三个不用管,因为这是分割前另外一块的开头。贴代码

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* sortList(ListNode* head) 
14     {
15         return sort(head,nullptr);                
16     }
17     ListNode* sort(ListNode* head,ListNode* tail)
18     {
19         if(!head)
20         return nullptr;
21         //
22         if(head->next == tail)
23         {
24             head->next = nullptr;
25             return head;
26         }
27         //分
28         ListNode* pointer_1 = head;
29         ListNode* pointer_2 = head;
30         while(pointer_2!=tail)
31         {
32             pointer_1 = pointer_1->next;
33             pointer_2 = pointer_2->next;
34             if(pointer_2!=tail)
35             pointer_2 = pointer_2->next;
36         }
37         ListNode* mid = pointer_1;
38         //分割时存在重叠部分,而这一部分会在分割到两个元素时被舍去,很巧妙的设计
39         ListNode* head_1 = sort(head,mid);
40         ListNode* head_2 = sort(mid,tail);
41         return merge(head_1,head_2);        
42     }
43     ListNode* merge(ListNode* head_1,ListNode* head_2)
44     {
45         ListNode* head = new ListNode(0);
46         ListNode* temp = head;
47         ListNode* temp_1 = head_1;
48         ListNode* temp_2 = head_2;
49         while(temp_1!=nullptr && temp_2!=nullptr)
50         {
51             if(temp_1->val > temp_2->val)
52             {
53                 temp->next = temp_2;
54                 temp_2 = temp_2->next;
55             }
56             else
57             {
58                 temp->next = temp_1;
59                 temp_1 = temp_1->next;
60             }
61             temp = temp->next;
62         }
63         if(temp_1)
64         temp->next = temp_1;
65         else if(temp_2)
66         temp->next = temp_2;
67         return head->next;
68     }
69 };

 修改了下分割时无重叠的方法,几个小细节改一下,贴代码

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* sortList(ListNode* head) 
14     {
15         if(!head)
16         return head;
17         ListNode* end = head;
18         while(end->next)
19         end = end->next;
20         return sort(head,end);                
21     }
22     ListNode* sort(ListNode* head,ListNode* tail)
23     {
24         if(head == nullptr)
25         return nullptr;
26         if(head == tail)
27         {
28             head->next = nullptr;
29             return head;
30         }
31         //分
32         ListNode* pointer_1 = head;
33         ListNode* pointer_2 = head;
34         while(pointer_2!=tail)
35         {
36             //由于分割时不存在重叠部分,于是只有在快指针能够推两次的情况下慢指针才会推一次
37             //为了两个元素时能够分割正确
38             pointer_2 = pointer_2->next;
39             if(pointer_2!=tail)
40             {
41                 pointer_1 = pointer_1->next;
42                 pointer_2 = pointer_2->next;
43             }
44         }
45         //cout<<pointer_1->next->val<<endl;
46         //cout<<pointer_2->val<<endl;
47         ListNode* mid = pointer_1->next;
48         //分割时不存在重叠部分
49         ListNode* head_1 = sort(head,pointer_1);
50         ListNode* head_2 = sort(mid,pointer_2);
51         //cout<<head_1->val<<endl;
52         return merge(head_1,head_2);        
53     }
54     ListNode* merge(ListNode* head_1,ListNode* head_2)
55     {
56         ListNode* head = new ListNode(0);
57         ListNode* temp = head;
58         ListNode* temp_1 = head_1;
59         ListNode* temp_2 = head_2;
60         while(temp_1!=nullptr && temp_2!=nullptr)
61         {
62             if(temp_1->val > temp_2->val)
63             {
64                 temp->next = temp_2;
65                 temp_2 = temp_2->next;
66             }
67             else
68             {
69                 temp->next = temp_1;
70                 temp_1 = temp_1->next;
71             }
72             temp = temp->next;
73             //cout<<temp->val<<endl;
74         }
75         if(temp_1)
76         temp->next = temp_1;
77         else if(temp_2)
78         temp->next = temp_2;
79         return head->next;
80     }
81 };

除了上述的自顶向下的方法,还有自下向顶的方法,首选以每个节点为单位进行两个两个的排序,以这种方式完成第一轮排序之后,就进行循环,将上述的子串的大小加倍,将两个各自完成排序的子串进行归并排序,以此类推,能够完成整个串的排序。代码的撰写中细节主要在于找到两个子串的头以及将子串分隔开。尤其是第二个子串,可能会出现元素不足甚至就没有元素的情况,所以需要单独的取出进行讨论。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* sortList(ListNode* head) 
14     {
15         if(!head)
16         return nullptr;
17         int length = 0;
18         ListNode* listSize = head;
19         while(listSize!=nullptr)
20         {
21             length++;
22             listSize = listSize->next;
23         }
24         //将newHead的next节点赋为head主要是为了之后的循环变量temp的使用
25         ListNode* newHead = new ListNode(0,head);
26         for(int subLength = 1 ; subLength < length ; subLength*=2)
27         {
28             ListNode* preHead = newHead;
29             ListNode* temp = newHead->next;
30             while(temp!=nullptr)
31             {
32                 //找到第一个head
33                 ListNode* head_1 = temp;
34                 for(int i = 1 ; i < subLength && temp->next!=nullptr ; i++)
35                 temp = temp->next;
36                 ListNode* head_2 = temp->next;
37                 temp->next = nullptr;
38                 temp = head_2;
39                 //找到第二个head
40                 for(int i = 1 ; i < subLength && temp!=nullptr &&  temp->next!=nullptr ; i++)
41                 temp = temp->next;
42                 ListNode* end = nullptr;
43                 //判断第二个部分中是否有元素,如果有,则将temp的next元素脱钩
44                 //如果无元素,则无需脱钩
45                 if(temp!=nullptr)
46                 {
47                     end = temp->next;
48                     temp->next = nullptr;
49                 }
50                 //合并
51                 ListNode* merged = merge(head_1,head_2);
52                 preHead->next = merged;
53                 while(preHead->next!=nullptr)
54                 preHead = preHead->next;
55                 temp = end;
56             }
57         }
58         return newHead->next;               
59     }
60     ListNode* merge(ListNode* head_1,ListNode* head_2)
61     {
62         ListNode* head = new ListNode(0);
63         ListNode* temp = head;
64         ListNode* temp_1 = head_1;
65         ListNode* temp_2 = head_2;
66         while(temp_1!=nullptr && temp_2!=nullptr)
67         {
68             if(temp_1->val > temp_2->val)
69             {
70                 temp->next = temp_2;
71                 temp_2 = temp_2->next;
72             }
73             else
74             {
75                 temp->next = temp_1;
76                 temp_1 = temp_1->next;
77             }
78             temp = temp->next;
79             //cout<<temp->val<<endl;
80         }
81         if(temp_1)
82         temp->next = temp_1;
83         else if(temp_2)
84         temp->next = temp_2;
85         return head->next;
86     }
87 };

 

上一篇:2021-10-01


下一篇:leetcode 148. 排序链表(归并排序 快慢指针 递归 迭代)