大厂面试算法题之链表

作者：程序员学长

2021 年 12 月 09 日
本文字数：18073 字
阅读完需：约 59 分钟

链表

全文概览

链表基础知识

链表的分类

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

单链表

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

双向链表

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

单向循环链表

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

双向循环链表

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

链表的定义

我们在刷 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]

复制代码

分析问题

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

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

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

代码实现

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=headfor 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个升序链表

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

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

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

示例如下所示：

  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

分析问题

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

我们首先将链表按照 k 个一组进行分组。对于最后一组，有可能元素个数不满足 k 个。
对于每一个分组，我们去判断元素的个数是否为 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}

分析问题

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

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

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

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

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)的排序算法有归并排序、快速排序和堆排序，其中最适合链表的排序算法是归并排序。

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

分割环节
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针走到链表的末尾时，慢指针恰好指向了链表的中点位置。
找到中点后，将链表在中点处分割成两个子链表。
然后递归的进行分割，直到分割后的链表只有一个节点或者为 Null。这时，分割的子链表都是有序的，因为只包含一个节点。
合并环节
将两个有序的链表合并成一个有序链表。我们可以采用双指针法求解。
递归执行，直到合并完成。

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。然后将链表拆分成子链表进行合并。

我们用 sublength 表示每次需要排序的子链表的长度，初始时 sublength=1。
每次将链表拆分成若干个长度为 sublength 的子链表（最后一个子链表的长度可能小于 sublength），按照每两个子链表一组进行合并，合并后即可以得到若干个长度为 sublength * 2 的有序子链表（最后一个子链表的长度可能小于 sublength * 2）。
将 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)。

判断一个链表是否为回文结构

问题描述

LeetCode 剑指 Offer II 027. 回文链表

给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。

示例：

输入：{1,2,2,1}

输出：true

说明：1 -> 2 -> 2 -> 1

分析问题

回文串是指正读反读都一样的字符串，最简单的是使用双指针法。但是对于链表这种数据结构来说，指针只能向一个方向移动，也就是说只能找到后继节点，没办法找到前驱节点。所以没办法使用双指针法，要想使用双指针，我们就需要把链表元素放入一个数组中，然后再去判断是否是回文，这需要 O（n）的空间复杂度，这里就不在赘述。大家可以去看第 44 题。

我们可以这么考虑，将链表的后半部分进行反转，然后将前半部分和后半部分进行比较，如果相同就代表是回文链表，否则不是回文链表。寻找链表的中点我们可以使用快慢指针的方式。

快慢指针寻找链表中点。

对链表的后半部分进行翻转

前半部分和后半部分进行比较。

class Solution:    def isPalindrome(self, head) -> bool:        #链表为空，直接返回true        if head is None:            return True
        #找到链表的中点        middle_point = self.middle_point(head)        second_start = self.reverse_list(middle_point.next)
        #判断前半部分和后半部分是否相等        result = True        first = head        second = second_start        while result and second is not None:            if first.val != second.val:                result = False            first = first.next            second = second.next
        #还原链表并返回结果        middle_point.next = self.reverse_list(second_start)        return result
    #快慢指针寻找中点    def middle_point(self, head):        fast = head        slow = head        while fast.next is not None and fast.next.next is not None:            fast = fast.next.next            slow = slow.next        return slow
    #翻转链表    def reverse_list(self, head):        previous = None        current = head        while current is not None:            next_node = current.next            current.next = previous            previous = current            current = next_node        return previous

复制代码

链表内指定区间反转

问题描述

LeetCode 92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例：

输入：head = [1,2,3,4,5]， left = 2，right = 4

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

分析问题

对于链表相关的题目，我们一定要先想清楚思路，搞懂指针移动的先后顺序。

对于这道题，我们可以采用头插法来求解。在链表反转的区间内，当我们每次遍历到一个节点时，就让该节点插入到反转部分的起始位置。如下图所示：

具体来说，我们定义三个指针 pre、cur、next 变量。

我们首先将 pre 移动到第一个要反转的节点的前面，即 pre->next=left
然后将指针 cur 移动到第一个要反转的节点位置上，即 cur=left，
然后将 cur->next 赋值给变量 next。
将 cur 的下一个节点指向 next 的下一个节点，即 cur->next=next->next
然后将 next 的下一个节点指向 pre 的下一个节点，即 next->next=pre->next
然后将 next 插入到链表头部，即 pre->next=next。
然后循环往复执行 3、4、5、6，直到反转完链表区间内的节点。

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

class Solution:    def reverseBetween(self, head, left, right):        #设置哨兵节点，对于链表相关的问题，我们通过设置哨兵节点        #可以省去边界条件的判断        dummynode = ListNode(-1)        #哨兵节点指向链表头        dummynode.next = head        pre = dummynode        #遍历，使得pre指向链表反转部分        #的第一个结点left        for _ in range(left - 1):            pre = pre.next        #cur指向链表反转部分的第一个节点        cur = pre.next        for _ in range(right - left):            next = cur.next            cur.next = next.next            next.next = pre.next            pre.next = next        return dummynode.next

复制代码

该算法的时间复杂度是 O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就完成了反转。空间复杂度是 O(1)，只用到了常数个变量。

删除有序链表中重复的元素-I

问题描述

LeetCode 83. 删除排序链表中的重复元素

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。

示例：

输入：{1,1,2}

输出：{1,2}

分析问题

因为给定的链表是排好序的，所以我们可以知道重复的元素在链表中出现的位置一定是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

开始时，我们定义一个指针 cur 指向链表的头结点，然后开始对链表进行遍历。如果 cur.val==cur.next.val 时，我们就将 cur.next 这个节点从链表中移除；如果不相同，我们将指针 cur 后移，即 cur=cur.next。当遍历完整个链表之后，我们返回链表的头结点即可。

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

class Solution:    def deleteDuplicates(self, head):        #如果链表为空，直接返回        if not head:            return head        #cur指向头结点        cur = head        #当cur.next不为空时        while cur.next:            #如果值相同，删除cur.next节点            if cur.val == cur.next.val:                cur.next = cur.next.next            #否则cur后移            else:                cur = cur.next        return head

复制代码

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

删除有序链表中重复的元素-II

问题描述

LeetCode 82. 删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。

示例:

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

输出：[1，2，5]

分析问题

由于给定的链表是有序的，所以链表中重复的元素在位置上肯定是相邻的。因此，我们可以对链表进行一次遍历，就可以删除重复的元素。

这里需要注意一点，由于可能会删除头结点 head，我们引入了一个哨兵节点 dummy，让 dummy.next=head，这样即使 head 被删除了，那么也会操作 dummy.next 指向新的链表头结点，所以最终返回 dummy.next 即可。

首先，我们让 cur 指针指向链表的哨兵节点，然后开始对链表进行遍历。如果 cur.next 与 cur.next.next 对应的元素值相同，那么我们就需要将 cur.next 以及后面所有值相同的链表节点全部删除，直到 cur.next 为空节点或者其元素值与其不同。如果 cur.next 与 cur.next.next 对应的元素值不相同，那么我们就可以将 cur 指向 cur.next。

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

class Solution:    def deleteDuplicates(self, head):        #如果链表为空，直接返回        if not head:            return head        #创建一个哨兵节点        dummy = ListNode(0)        dummy.next=head
        #开始时，将cur指向哨兵节点        cur = dummy        while cur.next and cur.next.next:            #如果cur.next.val和cur.next.next.val相同，删除重复元素            if cur.next.val == cur.next.next.val:                data = cur.next.val                while cur.next and cur.next.val == data:                    cur.next = cur.next.next            else:                cur = cur.next
        return dummy.next

复制代码

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

链表的奇偶重排

问题描述

LeetCode 328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

示例：

输入：{1，2，3，4，5，6}

输出：{1，3，5，2，4，6}

分析问题

要想把一个链表的奇数节点和偶数节点分别排在一起，我们可以先分离链表，把一个链表拆分成两个链表，其中一个是奇数链表，另一个是偶数链表，最后将偶数链表拼接在奇数链表后即可。

我们都知道，对于一个链表来说，相邻节点的奇偶性是不同的。原始链表的头节点 head 是奇数链表的头节点，head 的后一个节点是偶数链表的头节点，我们假设是 evenHead ，则 evenHead = head.next。我们维护两个指针 odd 和 even 分别指向奇数链表和偶数链表的最后一个节点，初始时 odd=head，even=evenHead。通过不断的更新 odd 和 even，将链表分割成奇数链表和偶数链表。

更新奇数节点，我们令 odd.next=even.next，此时奇数链表的最后一个节点指向了偶数节点 even 的后一个节点。然后令 odd=odd.next，此时 odd 变成了 even 的后一个节点。
更新偶数节点，我们令 even.next=odd.next，此时偶数节点的最后一个节点指向了奇数节点 odd 的后一个节点。然后令 even=even.next，此时 even 变成了 odd 的后一个节点。

通过以上两步，我们就完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完成。最后令 odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并。

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

class Solution:    def oddEvenList(self, head):        #如果链表为空，直接返回        if not head:            return head        #evenHead指向偶数链表的头节点        evenHead = head.next        #指向奇数链表和偶数链表的末尾节点        odd = head        even = evenHead        while even and even.next:            #奇数链表的末尾节点指向偶数节点的下一个节点            odd.next = even.next            #奇数链表末尾节点后移            odd = odd.next            #偶数链表的末尾节点指向奇数节点的下一个节点            even.next = odd.next            #偶数链表末尾节点后移            even = even.next
        #偶数链表连接到奇数链表的末尾        odd.next = evenHead        return head

复制代码

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

重排链表

问题描述

LeetCode 143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：L0 -> L1 -> ... -> Ln-1 -> Ln，将其重新排列后变成 L0 -> Ln -> L1 -> Ln-1 -> ...。不能只是单纯的改变节点的值，而需要实际的进行节点的交换。

示例：

输入： head = [1，2，3，4]

输出： [1，4，2，3]

###分析问题

首先，我们来观察一下链表重置前和重置后的变化。如下图所示：

我们可以知道，重置后的链表是将原链表的左半端和反转后的右半段进行节点交叉合并而成的，所有我们可以分三步来求解。

找到原链表的中点，将链表分割成左右两部分。
对后半部分进行反转。
建原链表的左半部分和反转后的右半部分进行合并。

class Solution:    def reorderList(self, head):        #如果链表为空，直接返回        if not head:            return        #寻找链表的中点，将链表分割成左右两部分        mid = self.middleNode(head)        left = head        right = mid.next        mid.next = None        #对右半部分的链表进行反转        right = self.reverseList(right)        #左右链表进行合并        self.mergeList(left, right)
    def middleNode(self, head):        #使用快慢指针法求中点        slow = fast = head        while fast.next and fast.next.next:            slow = slow.next            fast = fast.next.next        return slow
    #对链表进行反转    def reverseList(self, head):        prev = None        curr = head        while curr:            tmp = curr.next            curr.next = prev            prev = curr            curr = tmp        return prev
    #对两个链表进行合并操作    def mergeList(self, l1, l2):        #l1和l2的节点数量相差不会超过一个        #所以直接合并就好        while l1 and l2:            tmp1 = l1.next            tmp2 = l2.next
            l1.next = l2            l1 = tmp1
            l2.next = l1            l2 = tmp2

复制代码

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

链表中倒数最后 k 个节点

问题描述

LeetCode 剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第 k 个节点。为了符合大多数人的习惯，本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

输入：{1,2,3,4,5}，2

输出：{4,5}

分析问题

这道题比较简单，我们可以直接使用快慢指针来求解，开始时申请两个指针同时指向链表的头结点，记为 slow 和 fast，然后让 fast 先移动 k 步，再然后让两个指针 slow 和 fast 同时移动，使得 fast 和 slow 在移动的过程中总是相隔 k 个单位，当 fast 指针走到末尾的时候，此时 slow 正好指向的是倒数第 k 个位置。

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

class Solution:    def FindKthToTail(self, pHead, k):        #快慢指针同时执行头结点        slow=fast=pHead        #快指针移动k步        for i in range(0,k):            #如果还没走完k步就走到了链表尾，直接返回None            if not fast:                ‘return None            fast = fast.next        #两个指针同时移动,直到fast为空        while fast:            slow=slow.next            fast=fast.next
        return slow

复制代码

划分链表

问题描述

LeetCode 面试题 02.04. 分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

示例：

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

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

分析问题

简单来说，我们只需要维护两个链表 small 和 large 即可，使得 small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x 的节点。当我们遍历完链表之后，只需要将 small 链表的尾节点指向 large 链表的头结点即可完成分割链表的操作。

首先，我们创建两个节点 smallHead 和 largeHead 分别为两个链表的哑结点，这是为了方便的处理头结点为空的边界条件，同时 smallTail 和 largeTail 分别指向两个链表的末尾节点。开始时，smallHead=smallTail，largeHead=largeTail，然后从前往后遍历链表 head，判断当前节点的值是否小于 x，如果小于 x，就将 smallTail 的 next 指针指向该节点，否则将 largeTail 的 next 指针指向该节点。

遍历结束后，我们将 largeTail 的 next 指针置为空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用。然后将 smallTail 的 next 指针指向 largeHead 的 next 指针指向的节点，来将两个链表合并起来，最后返回 smallHead.next 即可。

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

class Solution(object):    def partition(self, head, x):        #创建两个哑结点        smallHead = smallTail = ListNode(0)        largeHead = largeTail = ListNode(0)        #遍历链表        while head:            #如果head.val<x,将当前节点插入small中，否则插入large中            if head.val < x:                smallTail.next=head                smallTail=smallTail.next            else:                largeTail.next=head                largeTail=largeTail.next            head=head.next        largeTail.next=None        #合并两个链表        smallTail.next=largeHead.next        return smallHead.next

复制代码

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

发布于: 3 小时前阅读数: 4

程序员学长

关注

程序员学长 2020.11.14 加入

公众号：程序员学长号主，专注分享算法、大数据、计算广告等技术

发布

暂无评论

创作场景

大厂面试算法题之链表

链表

全文概览

链表基础知识

链表的分类

单链表

双向链表

单向循环链表

双向循环链表

链表的定义

链表的操作

单链表的删除操作

向单链表中增加一个节点

解题有妙招

引入哑结点

双指针法

反转链表

问题描述

分析问题

代码实现

合并两个有序链表

问题描述

分析问题

问题升级

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

问题描述

分析问题

判断链表是否有环

问题描述

分析问题

优化

链表中环的入口结点

问题描述

分析问题

优化

删除链表倒数第 n 个节点

问题描述

分析问题

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

问题描述

分析问题

两个链表生成相加链表

问题描述

分析问题

单链表的排序

问题描述

分析问题

优化

判断一个链表是否为回文结构

问题描述

分析问题

链表内指定区间反转

问题描述

分析问题

删除有序链表中重复的元素-I

问题描述

分析问题

删除有序链表中重复的元素-II

问题描述

分析问题

链表的奇偶重排

问题描述

分析问题

重排链表

问题描述

链表中倒数最后 k 个节点

问题描述

分析问题

划分链表

问题描述

分析问题

程序员学长

评论