148 排序链表

发布于:2024-12-09 ⋅ 阅读:(140) ⋅ 点赞:(0)

在这里插入图片描述解题思路:
\qquad 题目希望能在 O ( n L o g n ) O(nLogn) O(nLogn)时间复杂度内解决问题,满足这个条件的常用排序算法有:快速排序(Quick Sort)、归并排序(Merge Sort)和堆排序(Heap Sort)。

  • 由于链表节点中的next指针,使节点按特定顺序链接。因而不适合频繁的移动元素,所以快速排序对于链表,用起来不是很方便。
  • 堆排序,是利用堆这一数据结构的特点进行排序,将待排序元素存入栈,每次取堆顶的元素,自然是有序的。但要将链表节点存入栈,需要重写堆的排序方法,略微有些麻烦。
  • 归并排序,将序列不断二分,对左右两个序列继续排序后,将返回的两个有序序列按顺序合并的排序算法。无论是二分,还是合并有序序列,都可以按照从左至右的顺序访问元素并完成,因此十分适合对链表排序。

\qquad 代码实现有几个注意的点:
\qquad 可以使用快慢指针,快速找到链表中间的节点;
\qquad 使用自定义节点做一个伪head,这样可以少判head为空的情况,返回时也要注意返回head->next;
\qquad 递归的终止条件,除了head为空之外,链表内只有一个元素的情况也要返回,不然会陷入死循环。

ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* slow;
        ListNode* fast = head;
        while(fast != nullptr)
        {
            if(fast == head) slow = head;
            else slow = slow->next;
            if(fast->next == nullptr) fast = nullptr;
            else fast = fast->next->next;
        }

        if(slow != nullptr)
        {
            fast = sortList(slow->next);
            slow->next = nullptr;
        }
        else fast = sortList(nullptr);
        slow = sortList(head);

        ListNode* joined = new ListNode(0);
        ListNode* curr = joined;
        while(slow != nullptr || fast != nullptr)
        {
            if(slow != nullptr && fast != nullptr)
            {
                if(slow->val <= fast->val)
                {
                    curr->next = slow;
                    slow = slow->next;
                }
                else {
                    curr->next = fast;
                    fast = fast->next;
                }
                curr = curr->next;
            }
            else if(slow == nullptr)
            {
                curr->next = fast;
                break;
            }
            else
            {
                curr->next = slow;
                break;
            }
        }
        return joined->next;
    }

网站公告

今日签到

点亮在社区的每一天
去签到