148 排序链表

题目

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

示例 1:

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

示例 2:

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

实现

思路:模仿并归排序的思路,典型的回溯算法。

如果待排的元素存储在数组中,我们可以用并归排序。而这些元素存储在链表中,我们无法直接利用并归排序,只能借鉴并归排序的思想对算法进行修改。

并归排序的思想是将待排序列进行分组,直到包含一个元素为止,然后回溯合并两个有序序列,最后得到排序序列。

对于链表我们可以递归地将当前链表分为两段,然后merge,分两段的方法是使用双指针法,p1指针每次走两步,p2指针每次走一步,直到p1走到末尾,这时p2所在位置就是中间位置,这样就分成了两段。

C# 语言

  • 状态:通过
  • 16 / 16 个通过测试用例
  • 执行用时: 124 ms, 在所有 C# 提交中击败了 100.00% 的用户
  • 内存消耗: 29 MB, 在所有 C# 提交中击败了 25.00% 的用户
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
 
public class Solution
{
    public ListNode SortList(ListNode head)
    {
        if (head == null)
            return null;
        return MergeSort(head);
    }
    
    private ListNode MergeSort(ListNode node)
    {
        if (node.next == null)
        {
            return node;
        }
        ListNode p1 = node;
        ListNode p2 = node;
        ListNode cut = null;
        while (p1 != null && p1.next != null)
        {
            cut = p2;
            p2 = p2.next;
            p1 = p1.next.next;
        }
        cut.next = null;
        ListNode l1 = MergeSort(node);
        ListNode l2 = MergeSort(p2);
        return MergeTwoLists(l1, l2);
    }

    private ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
        ListNode pHead = new ListNode(-1);
        ListNode temp = pHead;

        while (l1 != null && l2 != null)
        {
            if (l1.val < l2.val)
            {
                temp.next = l1;
                l1 = l1.next;
            }
            else
            {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }

        if (l1 != null)
            temp.next = l1;

        if (l2 != null)
            temp.next = l2;

        return pHead.next;
    }
}

Python 语言

  • 执行结果:通过
  • 执行用时:216 ms, 在所有 Python3 提交中击败了 75.99% 的用户
  • 内存消耗:20.7 MB, 在所有 Python3 提交中击败了 28.57% 的用户
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        return self.mergeSort(head)

    def mergeSort(self, node: ListNode) -> ListNode:
        if node.next is None:
            return node
        p1 = node
        p2 = node
        cute = None
        while p1 is not None and p1.next is not None:
            cute = p2
            p2 = p2.next
            p1 = p1.next.next
        cute.next = None
        l1 = self.mergeSort(node)
        l2 = self.mergeSort(p2)
        return self.mergeTwoLists(l1, l2)

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        pHead = ListNode(-1)
        temp = pHead
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next

        if l1 is not None:
            temp.next = l1
        if l2 is not None:
            temp.next = l2

        return pHead.next
浙ICP备19012682号