LeetCode题目之腾讯精选练习（50题）：排序链表

落日映苍穹つ 2024-04-19 11:02 66阅读 0赞

# 题目 #

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

**示例 1** :

输入: 4->2->1->3
    输出: 1->2->3->4

**示例 2** :

输入: -1->5->3->4->0
    输出: -1->0->3->4->5

## 实现代码 ##

public ListNode SortList(ListNode head)//转入列表排序
    {
        
        List<int> a = new List<int>();
        ListNode cur = head;
        ListNode sorted = new ListNode(0);
        ListNode cur2 = sorted;
        while (cur != null)
        {
        
            a.Add(cur.val);
            cur = cur.next;
        }
        a.Sort();
        foreach (var i in a)
        {
        
            cur2.next = new ListNode(i);
            cur2 = cur2.next;
        }
        return sorted.next;
    }
    public ListNode SortList(ListNode head)//从头到尾加入元素
    {
        
        if (head == null)
            return null;
    
        ListNode sorted = new ListNode(int.MinValue);
        sorted.next = new ListNode(head.val);
    
        ListNode cur = head.next;//记录未排序链表中的位置
        ListNode curs = sorted.next;//记录排序链表中的位置
        ListNode pre = sorted;//记录curs的前一个元素
    
        while (cur != null)
        {
        
            if (cur.val <= curs.val && cur.val >= pre.val)
            {
        
                pre.next = new ListNode(cur.val);
                pre.next.next = curs;
                cur = cur.next;
    
                curs = sorted.next;
                pre = sorted;
            }
            else if (cur.val > curs.val && curs.next != null)
            {
        
                pre = curs;
                curs = curs.next;
            }
            else if (cur.val > curs.val && curs.next == null)
            {
        
                curs.next = new ListNode(cur.val);
                cur = cur.next;
    
                curs = sorted.next;
                pre = sorted;
            }
        }
        return sorted.next;
    }

## 执行结果 ##

**执行结果**：通过  
**执行用时** : 164 ms, 在所有 C\# 提交中击败了78.72%的用户  
**内存消耗** : 30.2 MB, 在所有 C\# 提交中击败了6.25%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]  
第二个  
![在这里插入图片描述][20190917173034313.png]

## 小的总结 ##

刚开始想着先用最简单的办法完成，但其实是取巧的方法，忽略了链表的特性。之后按照链表设计了算法，但是没有巧妙的设计。看了官方题解后，知道了最符合题目要求的是归并排序，理解好理解，但代码很晦涩难懂，还需细细理解，总之先移植到C\#上成功运行了。

## 归并排序 ##

public ListNode SortList(ListNode head)//归并排序
    {
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        var p = head;
        int length = 0;
        while (p != null)
        {
        
            ++length;
            p = p.next;
        }
    
        for (int size = 1; size < length; size <<= 1)
        {
        
            var cur = dummyHead.next;
            var tail = dummyHead;
    
            while (cur != null)
            {
        
                var left = cur;
                var right = cut(left, size); 
                cur = cut(right, size); 
    
                tail.next = MergeTwoLists(left, right);
                while (tail.next != null)
                {
        
                    tail = tail.next;
                }
            }
        }
        return dummyHead.next;
    }
    
    public ListNode cut(ListNode head, int n)
    {
        
        var p = head;
        while (--n != 0 && p != null)
        {
        
            p = p.next;
        }
    
        if (p == null) return null;
    
        var next = p.next;
        p.next = null;
        return next;
    }
    public ListNode MergeTwoLists(ListNode l1, ListNode l2)//合并两个有序链表
    {
        
        var listHead = new ListNode(0);
        ListNode curr = listHead;
        int x, y;
        while (l1 != null || l2 != null)
        {
        
            x = (l1 != null) ? l1.val : int.MaxValue;
            y = (l2 != null) ? l2.val : int.MaxValue;
            if (x < y)
            {
        
                curr.next = new ListNode(x);
                if (l1 != null) l1 = l1.next;
            }
            else
            {
        
                curr.next = new ListNode(y);
                if (l2 != null) l2 = l2.next;
            }
            curr = curr.next;
        }
        return listHead.next;
    }

![在这里插入图片描述][20190917173846100.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f7413d4004ed4485aa66a59985e3c887.png
[20190917173034313.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a7f9a7297c764c0e8ac7f91d1d2a39e4.png
[20190917173846100.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8691b2ab374f4909b9d4e4af99f7691e.png