在链接列表中合并排序

我目前正在练习或面试,正在为链表问题进行合并排序。

给出了一个链接列表(has next 和 val 属性) 4-2-1-3 我应该把它分类 1-2-3-4 在里面 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)

其他部分是相同的,现在我有了相同的答案。但是,我不确定这一变化是如何产生影响的。