点击上方“小白学视觉”，选择加"星标"或“置顶”

重磅干货，第一时间送达

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

下载1：OpenCV-Contrib扩展模块中文版教程

在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

下载2：Python视觉实战项目52讲

在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。

下载3：OpenCV实战项目20讲

在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。

交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~