链表中的归并排序

Question

我目前正在练习或面试，正在为链表问题做归并排序。

给定一个链表（具有 next 和 val 属性），4-2-1-3，我应该将其排序为 1-2-3-4 in O(nlogn) .因此，我尝试对链表使用归并排序。下面是我的代码。

def sortList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """

    if head.next:

        # find mid point

        mid = fast = head
        while fast.next and fast.next.next:
            mid = mid.next
            fast = fast.next.next

        # split linkedList into two

        L = head
        R = mid.next
        mid.next = None

        # recursively call mergeSort to Left and Right Lists

        self.sortList(L)
        self.sortList(R)

        # pointers for merging

        newPtr = newHead = ListNode(-1)
        newHead.next = newPtr

        # merge and sort

        while L and R:
            if L.val < R.val:
                newPtr.next = L
                L = L.next
            else:
                newPtr.next = R
                R = R.next
            newPtr = newPtr.next
        # for remaining nodes
        while L:
            newPtr.next = L
            newPtr = newPtr.next
            L = L.next
        while R:
            newPtr.next = R
            newPtr = newPtr.next
            R = R.next

        return newHead.next

    else:
        return head

我觉得我的归并排序算法是正确的，但上面输入的结果让我 1-3-4 缺少 2。

我觉得我真的很接近，但我不确定我搞砸了哪一部分。

请帮忙。

编辑

我通过将 L 和 R 更改为 l1 和 l2 并更改

解决了这个问题

        self.sortList(L)
        self.sortList(R)

这个给

        L = self.sortList(l1)
        R = self.sortList(l2)

其他部分相同，现在我有相同的答案。但是，我不确定更改是如何产生差异的。

Answer 1

递归调用sortList时，局部函数变量R和L可能不再是各自链表段的头部。随后的合并操作将 "skip" 排序列表中位于原始节点之前的部分，导致输出不完整。

您的更改确保 R 和 L 具有每个子列表的有效头部，通过将它们重新分配给已排序链的头部来合并。

链表中的归并排序

Merge-sort in a Linked List

python

mergesort

linked-list