链表

全文概览

链表基础知识

链表的分类

链表是一种通过指针串联在一起的线性结构，主要分为单链表、双向链表和循环链表。

单链表

单链表中每一个节点是由两部分组成，一个是数据域、一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域为空。

双向链表

双向链表中的每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双向链表既可以向前查询也可以向后查询。

单向循环链表

单向循环链表是指首尾相连的单链表。

双向循环链表

双向循环链表是指首尾相连的双向链表。

链表的定义

我们在刷LeetCode的时候，由于链表的节点都默认定义好了，直接用就行了，但是在面试的时候，一旦要手写链表代码时，节点的定义是大家容易犯错的地方，所有我们来看一下定义链表节点的方式。

#单链表
class ListNode(object):
    def __init__(self, x):
        #数据域
        self.val = x
        #指针域
        self.next = None

链表的操作

单链表的删除操作

删除链表中的q节点，只需要执行p->next=q->next，即让p的指针域指向q的下一个节点。

向单链表中增加一个节点

在节点p后增加一个节点q，只需要执行q->next=p->next，p->next=q即可，这里一定要注意执行的先后顺序。如果先执行p->next=q，那么原链表的p->next的信息就丢失了。

解题有妙招

引入哑结点

哑结点也叫做哨兵节点，对于链表相关的题目，为了方便处理边界条件，一般我们都会引入哑结点来方便求解。首先我们来看一下什么是哑结点，哑结点是指数据域为空，指针域指向链表头节点的节点，它是为了简化边界条件而引入的。下面我们来看一个具体的例子，例如要删除链表中的某个节点操作。常见的删除链表的操作是找到要删元素的前一个元素，假如我们记为 pre。我们通过：pre->next=pre->next->next来执行删除操作。如果此时要删除的是链表的第一个结点呢？就不能执行这个操作了，因为链表的第一个结点的前一个节点不存在，为空。如果此时你设置了哑结点，那么第一个结点的前一个节点就是这个哑结点。这样如果你要删除链表中的任何一个节点，都可以通过pre->next=pre->next->next的方式来进行，这就简化的代码的逻辑。

双指针法

在求解链表相关的题目时，双指针也是非常常用的思想，例如对于求解链表有环问题时，我们申请两个指针，以一快一慢的速度在链表上行走，等他们相遇时，就可以知道链表是否有环；或者在求链表的倒数k个节点时，申请两个指针，一个指针先走k步，然后两个指针再同时向后移动，当先走的那个指针走到链表的末尾时，另一个指针恰好指向了倒数第k个节点。

反转链表

LeetCode206. 反转链表

问题描述

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

分析问题

首先，我们按照题目的要求，先把图画出来，然后再分析。

从图中我们可以看到，反转前和反转后指针的指向发生了反转。所以，我们在实现的过程中，我们可以通过调整链表的指针来达到反转链表的目的。

1. 我们定义两个指针pre和cur。pre表示已反转部分的头结点，cur表示还没有反转部分的头结点。开始时cur=head，pre=None
2. 每次让cur->next=pre，实现一次局部反转。
3. 局部反转完成后，cur和pre同时向前移动一位。
4. 循环上述过程，直到链表反转完成。

代码实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverse(self, head):
        cur = head
        #初始化时，pre为None
        pre = None
        while cur:
            next=cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

head=ListNode(1,None)
cur=head
for i in range(2,6):
    tmp=ListNode(i,None)
    cur.next=tmp
    cur=cur.next

s=Solution()
pre=s.reverse(head)

while pre!=None:
    print(pre.val)
    pre=pre.next

合并两个有序链表

LeetCode21. 合并两个有序链表

问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，我们需要合成后的链表满足单调不减规则。

示例：

输入: {1,3,5},{2,4,6}

返回值: {1,2,3,4,5,6}

分析问题

既然给定的两个链表都是有序的，那么我们可以判断两个链表的头结点的值的大小，将较小值的结点添加到结果中，然后将对应链表的结点指针后移一位，循环往复，直到有一个链表为空为止。

由于链表是有序的，所以循环终止时，那个非空的链表中的元素都比前面已经合并的链表中的元素大，所以，我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

首先我们需要先创建一个哨兵节点，然后将prehead指向链表l1和l2中比较小的一个。如果相等的话，指向任意一个即可。然后将较小值对应的链表的指针后移一位。

我们下面来看一下代码实现。

def mergeTwoLists(self, l1, l2):
        #合并后链表的哨兵结点
        head=ListNode(-1,None)
        pre=head
        #循环遍历，将两个链表中的较小值插入到合并后的链表中
        while l1 and l2:
            if l1.val <= l2.val:
                pre.next=l1
                l1=l1.next
            else:
                pre.next=l2
                l2=l2.next
            pre=pre.next
        #将剩余的非空链表插入到合并链表的后面
        if l1:
            pre.next=l1
        else:
            pre.next=l2

        return head.next

其实，我们这里也可以使用递归的方式来实现。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, l1, l2):
        #链表l1为空，不需要合并，直接返回l2
        if(l1==None):
            return l2
        #同理，l2为空，直接返回l1即可    
        if(l2==None):
            return l1

        if(l1.val<=l2.val):
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2

问题升级

LeetCode23. 合并K个升序链表

下面，我们来把问题升级一下，将两个有序链表合并改成多个有序链表合并，我们来看一下题目。

给定一个有序链表， 其中每个节点也表示有一个有序链表。结点包含两个类型的指针：

1. 指向主链表中下一个结点的指针。
2. 指向以此结点为头的链表。

示例如下所示：

  4 ->  9 -> 15 -> 19
  |     |     |     |
  7    13    18    28
  |           |     |
  8          21    37
  |                
  20               
  
 实现函数flatten()，该函数用来将链表扁平化成单个链表。例如上面的链表，输出链表为
 
  4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37 

题目要求我们把二维有序链表合并成一个单链表，我们来把问题简化一下，假设主链表只有两个节点，即这个二维链表变成如下所示。

 4 ->  9 
  |     |     
  7    13           旋转一下         4 -> 7 -> 8 -> 20
  |               ---------->       |
  8                                 9 -> 13
  |                
  20   

这不就是我们上面讲的两个有序链表合并吗？那如果主链表有多个节点呢？我们可以使用归并的思想，逐个去合并就好了，如下图所示。

下面我们来看一下代码如何实现。

class ListNode:
    def __init__(self, val=0, right=None, down=None):
        self.val = val
        self.right = right
        self.down = down

class Solution:
    def mergeTwoLists(self, l1, l2):
        #如果有一个链表为空，则合并后的链表就是另外一个
        if(l1==None):
            return l2
        if(l2==None):
            return l1

        if(l1.val<=l2.val):

            l1.down=self.mergeTwoLists(l1.down,l2)
            return l1
        else:
            l2.down=self.mergeTwoLists(l1,l2.down)
            return l2


    def flatten(self,root):
        if root== None or root.right == None:
            return root
        #把root->right 看作是已经有序的单链表，
        #然后通过递归来进行归并
        return self.mergeTwoLists(root, self.flatten(root.right))

链表中的节点每k个一组翻转

问题描述

LeetCode25. K 个一组翻转链表

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样。你不能更改节点中的值，只能更改节点本身。

例如：

给定的链表是：1 -> 2 -> 3 -> 4 -> 5

对于 k=2，你应该返回 2 -> 1 -> 4 -> 3 -> 5

对于 k=3， 你应该返回 3 -> 2 -> 1 -> 4 -> 5

分析问题

我们把这个问题进行拆分。

1. 我们首先将链表按照k个一组进行分组。对于最后一组，有可能元素个数不满足k个。

2. 对于每一个分组，我们去判断元素的个数是否为k，如果是k的话，我们进行反转，否则不需要进行反转。

我们下面来看一下代码实现。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    #反转链表，并且返回链表头和尾
    def reverse(self, head, tail):
        prev = tail.next
        p = head
        while prev != tail:
            next = p.next
            p.next = prev
            prev = p
            p = next
        return tail, head

    def reverseKGroup(self, head, k):
        #初始化一个哨兵节点，避免临界条件复杂的判断
        prehead = ListNode(0)
        #哨兵节点指向头结点
        prehead.next = head
        pre = prehead

        while head:
            tail = pre
            #查看剩余部分长度是否大于等于k
            for i in range(k):
                tail = tail.next
                #如果剩余长度小于k,则不需要反转，直接返回
                if not tail:
                    return prehead.next
            #tail指向子链表的尾部
            #所以next指向下一个子链表的头部
            next = tail.next
            #将链表进行反转，并返回链表头和尾
            head, tail = self.reverse(head, tail)
            #把子链表重新接回原链表
            pre.next = head
            tail.next = next
            pre = tail
            head = tail.next
            
        return prehead.next

判断链表是否有环

问题描述

LeetCode141. 环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例：

输入：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

分析问题

拿到这个问题，我们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否已经被访问过。如果被访问过，那么就代表该链表有环，直接返回。如果没有被访问过，我们就标记一下，然后接着去遍历下一个结点，直到遍历完整个链表为止。下面我们来看一下代码的实现。

def hasCycle(self, head):
    tags = set()
    while head:
        #表示已经被访问过了，代表有环
        if head in tags:
            return True
        tags.add(head)
        head = head.next
    return False

我们可以知道该算法的时间复杂度和空间复杂度都是O(n)。那我们有更好的解法吗？

优化

你可以这么思考，当有两名同学在操场上以不同的速度进行跑步，它们最终肯定会相遇。因为操场是环形的，如果在直线上跑，那他们肯定不会相遇。

我们假设同学1以速度1在跑，同学2以速度2在跑。

下面我们来看一下代码如何实现。

def hasCycle(self, head):
    #如果链表为空或者链表只有一个结点
    #直接返回false,因为不可能有环
    if not head or not head.next:
        return False
    #快慢指针
    slow = fast = head
    start = True

    while slow != fast || start:
        start=False
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next

    return True

我们这里引入了一个变量start表示是否是起跑。

可以看到该算法的空间复杂度降低为O(1)。

链表中环的入口结点

问题描述

LeetCode 剑指 Offer II 022. 链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

分析问题

拿到这个问题，我们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否已经被访问过。如果被访问过，就代表这个结点是链表中环的入口点，我们直接返回就好。如果没有被访问过，我们就标记一下，然后接着去遍历下一个结点，直到遍历完整个链表为止。下面我们来看一下代码的实现。

def EntryNodeOfLoop(self, pHead):
        tags = set()
        while pHead:
            #表示已经被访问过了，代表有环
            if pHead in tags:
                return pHead
            tags.add(pHead)
            pHead = pHead.next
        return None

我们可以看到该算法的时间复杂度和空间复杂度都是O(n)。

优化

我们这里也可以采用快慢指针来求解，就和上一题的解法类似，我们来看一下。

我们可以使用两个指针fast和slow。他们都从链表的头部开始出发，slow每次都走一步，即slow=slow->next，而fast每次走两步，即fast=fast->next->next。如果链表中有环，则fast和slow最终会在环中相遇。

我们假设链表中环外的长度为a，show指针进入环后又走了b的距离与fast相遇，此时fast指针已经绕着环走了n圈。所以快指针一共走了a+n(b+c)+b=a+(n+1)b+nc的距离，我们知道快指针每次走2步，而慢指针每次走一步，所以，我们可以得出快指针走的距离是慢指针的两倍，即a+(n+1)b+nc=2(a+b)，所以a=c+(n-1)(b+c)。这里你会发现：从相遇点到入环的距离c，再加上n-1圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现slow和fast相遇时，我们再额外使用一个指针ptr指向链表头部，然后它和slow指针每次都向后移动一个位置。最终，他们会在入环点相遇。

Tips: 你也许会有疑问，为什么慢指针在第一圈没走完就会和快指针相遇呢？我们来看一下，首先，快指针会率先进入环内。然后，当慢指针到达环的入口时，快指针在环中的某个位置，我们假设此时快指针和慢指针的距离为x，若x=0，则表示在慢指针刚入环时就相遇了。我们假设环的长度为n，如果看成快指针去追赶慢指针，那么快指针需要追赶的距离为n-x。因为快指针每次都比慢指针多走一步，所以一共需要n-x次就能追上慢指针，在快指针遇上慢指针时，慢指针一共走了n-x步，其中x>=0，所以慢指针走的路程小于等于n，即走不完一圈就会相遇。

下面，我们来看一下代码实现。

def detectCycle(head):
    if not head:
        return None
    #快慢指针
    slow = head
    fast = head
    while True:
        if not fast or not fast.next:
            return None
        fast=fast.next.next
        slow=slow.next
        #相遇时，跳出循环
        if fast == slow:
            break

    ptr = head
    while ptr != slow:
        ptr=ptr.next
        slow=slow.next
    return ptr

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

删除链表倒数第n个节点

问题描述

LeetCode 剑指 Offer II 021. 删除链表的倒数第 n 个结点

给定一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。

示例：

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

分析问题

这个问题最简单的求解方式就是遍历一遍链表，获取到链表的长度m，然后求出倒数第n个结点的位置m-n+1，然后再遍历一次链表，找到第m-n+1的位置，删掉这个结点就好。其实，我们这里可以使用双指针法，只需要遍历一次链表就可以解决问题。

首先，我们可以设置两个指针slow和fast都指向头结点，然后让fast先走n步，之后slow和fast一起走，直到fast.next为空为止，这是slow指向的就是倒数第n+1个结点，我们通过slow.next=slow.next.next就可以把倒数第n个结点删掉。

下面我们来看一下代码的实现。

    def removeNthFromEnd(self,head,n):    
        #左右指针指向头结点
        slow = fast = head
        #fast先走n步
        while n>0 and fast:
            fast = fast.next
            n=n-1
            
        if not fast:
            return head.next
        
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head

该算法只遍历一遍链表，所以时间复杂度是O(n)，空间复杂度是O(1)。

两个链表的第一个公共结点

问题描述

LeetCode 剑指 Offer 52. 两个链表的第一个公共节点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

要求：空间复杂度是O(1)，时间复杂度是O(m+n)。

示例：

分析问题

这个问题最直观的想法就是遍历链表headA，然后把headA中的所有每个节点都加入到集合中。然后再循环遍历链表headB，判断结点是否在集合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，继续遍历，直到结束。如果headB的所有结点都不在集合中，则表明不相交，直接返回null。

def getIntersectionNode(headA,headB):
    nodes=set()
    while headA:
        nodes.add(headA)
        headA=headA.next
    while headB:
        if nodes.__contains__(headB):
            return headB
        headB=headB.next
    return None

该算法的时间复杂度是O(m+n)，空间复杂度是O(n)。其中m和n分别是链表headA和headB的长度。

由于题目要求时间复杂度是O(m+n)，空间复杂度是O(1)。我们这里可以使用双指针法将空间复杂度降低到O(1)。我们分别用两个指针p1和p2分别指向headA和headB，然后同时移动指针p1和p2。当p1到达headA的末尾时，让p1指向headB，当p2到达headB的末尾时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。

Tips:假设headA不相交的部分是a，headB不相交的部分是b，公共部分是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，可以知道p1和p2指针同时到达第一个公共结点；当a不等于b时，在p1移动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，然后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。

def getIntersectionNode(headA,headB):
    p1 = headA
    p2 = headB

    while p1 != p2:
        if p1:
            p1=p1.next
        else:
            p1=headB
        if p2:
            p2=p2.next
        else:
            p2=headA
    return p1

两个链表生成相加链表

问题描述

LeetCode 剑指 Offer II 025. 链表中的两数相加

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。

示例：

输入：[9,3,7]，[6,3]

返回值：{1,0,0,0}

分析问题

由于两个数字相加是从个位数开始，然后再十位数、百位数。对于的链表中，我们需要将两个链表进行右端对齐，然后从右往左进行计算。

要想让两个链表右端对齐，我们有两种实现方式。

1. 将两个链表进行反转，然后直接求和。
2. 借助栈这种先进后出的特性，来实现链表的右端对齐。

我们先来看一下如何使用链表反转来实现。

class Solution(object):
    def reverse(self, head):
        cur = head
        #初始化时，pre为None
        pre = None
        while cur:
            next=cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre
    def addTwoNumbers(self, l1, l2):
        #将两个链表翻转
        l1 = self.reverse(l1)
        l2 = self.reverse(l2)
        head=ListNode(0)
        pre=head
        #代表是否进位
        carray=0
        while l1 or l2:
           v1=l1.val if l1 else 0
           v2=l2.val if l2 else 0
           sum=v1+v2+carray
           #进位数
           carray=int(sum/10)
           tmp=sum%10
           node=ListNode(tmp)
           pre.next=node
           pre=pre.next
           if l1:
               l1=l1.next
           if l2:
               l2=l2.next
        if carray==1:
            node=ListNode(carray)
            pre.next=node
        
        return self.reverse(head.next)

下面我们来看一下如何使用栈来求解。我们首先将两个链表从头到尾放入两个栈中，然后每次同时出栈，就可以实现链表的右端对齐相加，我们来看一下代码如何实现。

def addTwoNumbers(l1, l2):
    #申请两个栈
    stack1=[]
    stack2=[]
    #l1入栈
    while l1:
        stack1.append(l1.val)
        l1 = l1.next
    while l2:
        stack2.append(l2.val)
        l2 = l2.next

    head = None
    carry = 0

    while stack1 and stack2:
        num = stack1.pop() + stack2.pop() + carry
        #求进位数
        carry=int(num/10)
        tmp=num%10
        node = ListNode(tmp)
        node.next = head
        head = node


    s = stack1 if stack1 else stack2
    while s:
        num = s.pop() + carry
        carry = int(num / 10)
        tmp = num % 10
        node = ListNode(tmp)
        node.next = head
        head = node

    if carry==1:
        node = ListNode(carry)
        node.next = head
        head = node
    return head

单链表的排序

问题描述

LeetCode 148. 排序链表

给定一个节点数为n的无序单链表，对其按升序排序。

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)。

示例：

输入：[-1,0,-2]

返回值：{-2,-1,0}

分析问题

由于题目要求时间复杂度是O(nlogn)，那时间复杂度是O(nlogn)的排序算法有归并排序、快速排序和堆排序，其中最适合链表的排序算法是归并排序。

归并排序是基于分治思想，最容易想到的就是自顶向下的递归实现。自顶向下的递归实现主要包括二个环节。

1. 分割环节

   • 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针法，快指针每次移动2步，慢指针每次移动1步，当快指针走到链表的末尾时，慢指针恰好指向了链表的中点位置。

   • 找到中点后，将链表在中点处分割成两个子链表。

   • 然后递归的进行分割，直到分割后的链表只有一个节点或者为Null。这时，分割的子链表都是有序的，因为只包含一个节点。

2. 合并环节

   • 将两个有序的链表合并成一个有序链表。我们可以采用双指针法求解。
   • 递归执行，直到合并完成。

class Solution:
    def sortList(self, head):
        #如果链表为空或者只包含一个节点，递归终止
        if not head or not head.next:
            return head
        #使用快慢指针法来寻找链表的中点
        slow=head
        fast=head.next
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
        #slow指向的就是链表的中点，将链表在中点处进行分割
        head2=slow.next
        slow.next=None
        #递归的切割分割链表
        left = self.sortList(head)
        right = self.sortList(head2)
        #合并链表，使用双指针法
        tmp = res = ListNode(0)
        while left and right:
            if left.val < right.val:
                tmp.next=left
                left=left.next
            else:
                tmp.next=right
                right=right.next
            tmp=tmp.next
        if left:
            tmp.next=left
        else:
            tmp.next=right
        return res.next

该算法的时间复杂度是O(n)。由于自顶向下是通过递归来实现的，如果考虑递归调用栈的栈空间，那么该算法的空间复杂度是O(logn)。

优化

我们也可以采用自底向上的方法来求解。

首先，我们求出链表的长度length。然后将链表拆分成子链表进行合并。

1. 我们用sublength表示每次需要排序的子链表的长度，初始时sublength=1。
2. 每次将链表拆分成若干个长度为sublength的子链表（最后一个子链表的长度可能小于sublength），按照每两个子链表一组进行合并，合并后即可以得到若干个长度为sublength * 2的有序子链表（最后一个子链表的长度可能小于sublength * 2）。
3. 将sublength的值加倍，重复第二步，然后对更长的有序子链表进行合并，直到有序子链表的长度大于或等于链表的长度，这样整个链表的排序就完成了。

我们来看一下代码的实现。

class Solution:
    def sortList(self, head):
        #合并两个有序链表
        def merge(head1, head2):
            #哨兵节点
            dummyHead = ListNode(0)
            temp=dummyHead

            while head1 and head2:
                if head1.val <= head2.val:
                    temp.next = head1
                    head1 = head1.next
                else:
                    temp.next = head2
                    head2 = head2.next
                temp = temp.next
            if head1:
                temp.next = head1
            else:
                temp.next = head2

            return dummyHead.next

        #如果链表为空，直接返回
        if not head:
            return head
        #遍历一遍链表，求出链表的长度
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        #创建一个哨兵节点,指向链表头
        dummyHead = ListNode(0)
        dummyHead.next=head

        #初始时，子链表的长度为1
        subLength = 1

        while subLength < length:

            prev=dummyHead
            cur=dummyHead.next

            while cur:
                #截取长度为subLength的子链表head1
                head1 = cur
                for i in range(1, subLength):
                    if cur.next:
                        cur = cur.next
                    else:
                        break

                head2 = cur.next
                cur.next = None

                #截取长度为subLength的子链表head2
                cur = head2
                for i in range(1, subLength):
                    if cur and cur.next:
                        cur = cur.next
                    else:
                        break

                #截取完后剩余的链表节点
                surplus_head = None
                if cur:
                    surplus_head = cur.next
                    cur.next = None
                #将两个有序链表进行合并
                merged = merge(head1, head2)
                #将排好序的链表插入到新生成的链表里
                prev.next = merged

                #将指针移动到链表的末尾
                while prev.next:
                    prev = prev.next

                #继续合并剩余的节点
                cur=surplus_head
            subLength = subLength * 2

        return dummyHead.next

该算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。

由于篇幅长度限制，只能放这么多了，全文在以下链接中

大厂面试题之链表