leetcode.148.排序链表——归并排序

水深无声 2022-12-23 00:42 211阅读 0赞

# leetcode.148.排序链表 #

我们可以用[147. 对链表进行插入排序][147.]的方法来解。

class Solution { 
    public:
        ListNode* sortList(ListNode* head) { 
            //1.首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
            if (head == nullptr) { 
                return head;
            }
            //2.创建哑节点 dummyHead，令 dummyHead.next = head。引入哑节点是为了便于在 head 节点之前插入节点。
            ListNode* dummyHead = new ListNode(0);
            dummyHead->next = head;
            //3.维护 lastSorted 为链表的已排序部分的最后一个节点，初始时 lastSorted = head。
            ListNode* lastSorted = head;
            //4.维护 curr 为待插入的元素，初始时 curr = head.next。
            ListNode* curr = head->next;
    
            while (curr != nullptr) { 
                //5.比较 lastSorted 和 curr 的节点值。
                //若 lastSorted.val <= curr.val，说明 curr 应该位于 lastSorted 之后，
                //将 lastSorted 后移一位，curr 变成新的 lastSorted。
                if (lastSorted->val <= curr->val) { 
                    lastSorted = lastSorted->next;
                }
                else { 
                    //否则，从链表的头节点开始往后遍历链表中的节点，寻找插入 curr 的位置。令 prev 为插入 curr 的位置的前一个节点，
                    ListNode* prev = dummyHead;
                    while (prev->next->val <= curr->val) { 
                        prev = prev->next;
                    }
                    //进行如下操作，完成对 curr 的插入
                    lastSorted->next = curr->next;
                    curr->next = prev->next;
                    prev->next = curr;
                }
    
                //6.令 curr = lastSorted.next，此时 curr 为下一个待插入的元素。
                //7.重复第 5 步和第 6 步，直到 curr 变成空，排序结束。
                //8.返回 dummyHead.next，为排序后的链表的头节点。
    
                curr = lastSorted->next;
            }
    
            head = dummyHead->next;
            delete dummyHead;
            return head;
        }
    };

还不错，通过了。

执行用时：952 ms, 在所有 C++ 提交中击败了5.04%的用户
    内存消耗：28.9 MB, 在所有 C++ 提交中击败了40.20%的用户

你也可以用归并排序  
![在这里插入图片描述][6a8c14aa6c63d934481945b560b39cc7.png_pic_center]  
图片来自[leetcode][]

class Solution { 
        public ListNode sortList(ListNode head) { 
            return sortList(head, null);
        }
    
        public ListNode sortList(ListNode head, ListNode tail) { 
            if (head == null) { 
                return head;
            }
            if (head.next == tail) { 
                head.next = null;
                return head;
            }
            ListNode slow = head, fast = head;
            while (fast != tail) { 
                slow = slow.next;
                fast = fast.next;
                if (fast != tail) { 
                    fast = fast.next;
                }
            }
            ListNode mid = slow;
            ListNode list1 = sortList(head, mid);
            ListNode list2 = sortList(mid, tail);
            ListNode sorted = merge(list1, list2);
            return sorted;
        }
    
        public ListNode merge(ListNode head1, ListNode head2) { 
            ListNode dummyHead = new ListNode(0);
            ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
            while (temp1 != null && temp2 != null) { 
                if (temp1.val <= temp2.val) { 
                    temp.next = temp1;
                    temp1 = temp1.next;
                } else { 
                    temp.next = temp2;
                    temp2 = temp2.next;
                }
                temp = temp.next;
            }
            if (temp1 != null) { 
                temp.next = temp1;
            } else if (temp2 != null) { 
                temp.next = temp2;
            }
            return dummyHead.next;
        }
    }
    
    //作者：LeetCode-Solution

注意，这里快慢指针的写法

ListNode slow = head, fast = head;
        while (fast != tail) { 
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) { 
                fast = fast.next;
            }
        }

[147.]: https://leetcode-cn.com/problems/insertion-sort-list/
[6a8c14aa6c63d934481945b560b39cc7.png_pic_center]: /images/20221120/a7d5b2281dbe4da49b68c808a234f02f.png
[leetcode]: https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/