算法工程师面试必考项—

AI作者：田旭

AI编辑：田旭

1 知识点

1.1 什么是链表

提到链表，我们大家都不陌生，在平时的编码中我们也或多或少地使用过这个数据结构。算法（第4版） (豆瓣)一书中对链表的定义如下：

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

1.2 链表结构

1.2.1 单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

1.2.2 双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）。

一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

1.2.3 循环链表

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存，假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

指向整个列表的指针可以被称作访问指针。

用单向链表构建的循环链表

1.3链表相关的核心点

null/nil 异常处理
dummy node 哑巴节点
快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点

2 常见题型

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

思路：直接法，遇到重复就跳过

class Solution:    def deleteDuplicates(self, head: ListNode) -> ListNode:        cur = head        while cur and cur.next:            if cur.val == cur.next.val:                cur.next = cur.next.next            else:                cur = cur.next        return head

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

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

思路：定义哑节点指向链表头，定义双指针，一个指向当前节点，一个指向前一个节点。当有重复的元素时，cur指向下一位，直到下一位与当前节点不相等，用flag标记表示有重复数字，当循环完毕，pre的下一位指向cur的下一位，flag标记归位

当没有重复数字，pre指向cur

class Solution:    def deleteDuplicates(self, head: ListNode) -> ListNode:        if not head or not head.next:  # 空链表或单即节点链表            return head
        dummy = ListNode(0)    # 定义哑节点        dummy.next = head        pre = dummy            # 哑节点指针        cur = head             # 链表指针        flag = False           # 标记是否重复        while cur:            while cur.next and pre.next.val == cur.next.val:                cur = cur.next   # 将所有重复节点标记为True                flag = True            if flag is True:     # 重复节点就跳过                pre.next = cur.next                flag = False            else:                pre = cur        # 不重复就下一个节点            cur = cur.next        return dummy.next

206. 反转链表

反转一个单链表。

思路1：迭代，每次存储前一个节点，并让当前节点的next指针指向前一个节点

思路2：递归，假设我子节点下的所有节点都已经反转好了，现在就剩我和我的子节点没有完成最后的反转了，所以反转一下我和我的子节点。

# 迭代class Solution:    def reverseList(self, head: ListNode) -> ListNode:        pre = None        cur = head        while cur:            temp = cur.next   # 存储节点的下一位            cur.next = pre    # 指向前驱节点            pre = cur                     cur = temp        # cur指向原来的下一位        return pre

# 递归class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        p = self.reverseList(head.next)        head.next.next = head        head.next = None        return p

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路：用双指针法，现将慢指针移动到要反转的部分的前一个节点，用另一个指针指向慢指针后面的节点，然后两两交换节点

class Solution:    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:        dummy = ListNode(None)        dummy.next = head        pre = dummy        for i in range(1, m):            pre = pre.next         # 前驱指针移动到位置m        cur = pre.next        for i in range(m, n):      # 两两交换节点            temp = cur.next                    cur.next = temp.next   # cur一直不变，只修改指针到下一个位置            temp.next = pre.next   # temp.next指向pre的next，也就是最新的第m个位置            pre.next = temp        # 更新temp为最新的第m个位置        return pre

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：建立新链表，依次按升序链接两个链表的元素

class Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        dummy = ListNode(None)        pre = dummy        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        pre.next = l1 if l1 else l2        return dummy.next

86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

思路：创建双链表，一个存储小于x的值，一个存储大于x的值

class Solution:    def partition(self, head: ListNode, x: int) -> ListNode:        before = befornHead = ListNode(None)        after = afterHead = ListNode(None)        while head:            if head.val < x:                before.next = head                before = before.next            else:                after.next = head                after = after.next            head = head.next            after.next = None        before.next = afterHead.next        return befornHead.next

148. 排序链表

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

思路：归并排序，找中点和合并操作

# 归并排序（递归），空间复杂度O(n)class Solution:    def sortList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        slow, fast = head, head.next        while fast and fast.next:            slow, fast = slow.next, fast.next.next        mid = slow.next        slow.next = None        left = self.sortList(head)        right = self.sortList(mid)        h = res = ListNode(0)        while left and right:            if left.val < right.val:                 h.next, left = left, left.next            else:                 h.next, right = right, right.next            h = h.next        h.next = left if left else right        return res.next

# 快速排序class Solution:    def sortList(self, head: ListNode) -> ListNode:        if head is None:            return head        # 分成三个链表，分别是比轴心数小，相等，大的数组成的链表        big = None        small = None        equal = None        cur = head        while cur:            temp = cur            cur = cur.next            if temp.val < head.val:                temp.next = small                small = temp            elif temp.val > head.val:                temp.next = big                big = temp            else:                temp.next = equal                equal = temp        # 拆完各自排序即可，equal 无需排序        big = self.sortList(big)        small = self.sortList(small)
        ret = ListNode(None)        cur = ret        # 将三个链表组合成一起        # 可以同时返回链表的头指针和尾指针加速链表的合并。        for p in [small, equal, big]:            while p is not None:                cur.next = p                p = p.next                cur = cur.next            cur.next = None        return ret.next

143. 重排链表

给定一个单链表 L：L0→L1→…→L**n-1→Ln ，将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…

思路：找到中点断开，翻转后面部分，然后合并前后两个链表

class Solution:    def reorderList(self, head: ListNode) -> None:        """        Do not return anything, modify head in-place instead.        """        if not head or not head.next:            return head        slow, fast = head, head        # 找到链表中点        while fast.next and fast.next.next:               slow = slow.next            fast = fast.next.next        # 反转后半部分        print(slow.next)        right = None        cur = slow.next        while cur:            temp = cur.next            cur.next = right            right = cur            cur = temp        # 将反转的后半部分插入到前半部分        left = head        while left and right:            slow.next = right.next            right.next = left.next            left.next = right            left = right.next            right = slow.next

141. 环形链表

给定一个链表，判断链表中是否有环。

思路1：哈希表，统计每个元素出现的次数

思路2：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1

# 哈希表class Solution:    def hasCycle(self, head: ListNode) -> bool:        dic = {}        while head:            if head in dic:                return True            else:                dic[head] = 1            head = head.next        return False

# 快慢指针class Solution:    def hasCycle(self, head: ListNode) -> bool:        if head is None or head.next is None:            return False        slow = head        fast = slow.next        while fast and fast.next:            fast = fast.next.next            slow = slow.next            if fast == slow:                return True        return False

142. 环形链表 II

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

思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点

class Solution:    def detectCycle(self, head: ListNode) -> ListNode:        fast, slow = head, head        while True:            if not (fast and fast.next):                return             slow = slow.next            fast = fast.next.next            if slow == fast:                break        fast = head        while fast != slow:            fast = fast.next            slow = slow.next        return fast

138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。

思路：1、hash 表存储指针，2、复制节点跟在原节点后面

class Solution:    def copyRandomList(self, head: 'Node') -> 'Node':        if not head:            return        dic = {}        dic[None] = None        cur = head        while cur:            if cur not in dic:                dic[cur] = Node(cur.val)     # 将当前未拷贝的节点放入字典中            if cur.random not in dic:                dic[cur.random] = Node(cur.random.val)   # 将当前未拷贝的random指针放入字典中            dic[cur].random = dic[cur.random]            if cur.next not in dic:                dic[cur.next] = Node(cur.next.val)     # 将当前未拷贝的next指针放入字典中            dic[cur].next = dic[cur.next]            cur = cur.next        return dic[head]

234. 回文链表

请判断一个链表是否为回文链表。

思路1：将值复制到数组中，时间复杂度O(n)，空间复杂度O(n)

思路2：快慢指针，先找到链表中点，然后反转后半部分，再与前半部分比较，时间复杂度O(n)，空间复杂度O(1)

# 将值复制到数组中class Solution:    def isPalindrome(self, head: ListNode) -> bool:        visit = []        cur = head        while cur:            visit.append(cur.val)            cur = cur.next        return visit == visit[::-1]

# 找中点 -> 反转 -> 比较class Solution:    def isPalindrome(self, head: ListNode) -> bool:        pre = None        slow, fast = head, head        while fast and fast.next:            slow = slow.next      # 使慢指针指向中间节点            fast = fast.next.next        while slow:  # 反转后半部分，pre指向反转部分            temp = slow.next            slow.next = pre            pre = slow            slow = temp        while head and pre:   # 比较两部分是否相同            if head.val != pre.val:                return False            head = head.next            pre = pre.next        return True