| Python数据结构与算法篇（六） | 您所在的位置：网站首页 › 词根anx什么意思 › Python数据结构与算法篇（六） |
Python数据结构与算法篇（六）
|
这一部分的内容，前面的大佬总结的挺多，这里进行汇总，方便和大家一起学习和回顾，欢迎大家继续补充。 1 链表和数组作为线性表的两种存储方式————链表和数组，这对相爱相杀的好基友有着各自的优缺点。接下来，我们梳理一下这两种方式。 数组，所有元素都连续的存储于一段内存中，且每个元素占用的内存大小相同。这使得数组具备了通过下标快速访问数据的能力。 但连续存储的缺点也很明显，增加容量，增删元素的成本很高，时间复杂度均为 O ( n ) O(n) O(n)。增加数组容量需要先申请一块新的内存，然后复制原有的元素。如果需要的话，可能还要删除原先的内存。 
删除元素时需要移动被删除元素之后的所有元素以保证所有元素是连续的。增加元素时需要移动指定位置及之后的所有元素，然后将新增元素插入到指定位置，如果容量不足的话还需要先进行扩容操作。 
总结一下数组的优缺点： 优点：可以根据偏移实现快速的随机读写。缺点：扩容，增删元素极慢。上面对数组增删元素的操作表明使用数组需要注意的东西真的很多很多，这样一来，我们就开始说说链表，链表也是一种数据结构，它弥补了数组带来的诸多不便，让我们可以任意为一些数据进行空间的分配，根据需要进行内存单元的开辟。 链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，由若干个结点组成，在每一个结点里存到下一个结点的指针(Next)。采用动态分配存储单元方式。它能够有效地节省存储空间（同数组比较）。结点结构如下图所示： 
一般来讲，链表中只会有一个结点的指针域为空，该结点为尾结点，其他结点的指针域都会存储一个结点的内存地址。链表中也只会有一个结点的内存地址没有存储在其他结点的指针域，该结点称为头结点。 
对于链表而言，分为静态链表和动态链表，根据处理数据的方向又分为单向链表和双向链表。对于链表的更多操作，请阅读 Python数据结构与算法篇（四）-- 链表的实现 小结： 从本质上来讲，链表与数组的确有相似之处，他们的相同点是都是线性数据结构，这与树和图不同，而它们的不同之处在于数组是一块连续的内存，而链表可以不是连续内存，链表的节点与节点之间通过指针来联系。 2 常见链表问题解决思路 2.1 单链表的反转方法一：头插法（迭代法） 算法思想：逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中）， 使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。 方法二：递归法： 算法思想：从后向前改变指向，可以理解成向后的箭头变成了向前的箭头 方法三：三指针法 算法思想：从前向后改变指向，可以理解成向后的箭头变成了向前的箭头 2.2 单链表的删除某一结点方法一：遍历 思路：查找到所要删除的节点，以及其前驱节点，让其前驱节点，指向其后继节点 方法二：置换法（移花接木） 思路：明确要删除的节点后，把其后继节点复制到该节点上，然后删除那个后继节点，也等于变相的删除节点（注意如果删除的是尾节点 删除的链表只有一个节点） 2.3 在当前节点前插入一个数据方法一：遍历 思路：找出当前结点的前驱节点，完成插入； 方法二：置换法 思路：把插入节点的数据放到新节点上，把新节点的数据放到插入节点的数据上，这样我们就可以实现在当前节点前插入一个节点了。 2.4 查找链表的中间结点快慢指针法 思路：给一个快指针，让快指针每次移动两步，给一个慢指针，让慢指针每次移动一步，最后结果就是快指针移动到最后一个节点，慢指针最后移动到了中间的节点上。 设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast 向后走两次，slow 向后走一次，直到 fast 无法向后走两次。这使得在每轮移动之后。fast 和 slow 的距离就会增加一。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点，当 n 为 偶数时，slow 恰好指向中间两个结点的靠后一个。 
2.5 单链表的倒数第k个结点
方法一：正数转换法 思路：遍历一遍单链表，记录单链表的长度，倒数第k个，即正数 length-k+1 个，在重头遍历一次便能够找到 方法二：快慢指针法 思路：一个指针先走k步，然后两个指针同时走，当先走的那个指针指向空的时候，后面的指针所指即为倒数第K个节点。 设有两个指针 p 和 q，初始时均指向头结点。首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1 个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。可以参考下图来理解： 
2.6 对称单链表
1. 知道链表的长度 思路：根据对称来确定两个指针的位置，对所指向的元素进行判断，不断前进指针 2. 链表长度未知 思路1：将前一半的节点压入栈中，并将当前节点继续遍历，每遍历一个都与栈弹出的节点相比较，若不同则不是。额外空间复杂度 O(N/2)。 思路2：不使用辅助空间 两个指针，一个指向头 first，指向头的后继节点 last；first 走一步，last走两步；直到 last 为空或 last 的后继节点为空，此时 first 指向（链表长度为奇数，指向中间；为偶数，指向一半）；然后 fisrt 向后走，再申请一个节点指向头，不断进行比较，直到 first 指向空。 2.7 单链表是否有环方法一：map表法 算法思想：每走一步将走过的节点使用map表存储起来，当遇到第一个在map中存在的节点时，就说明回到了出发点，即链表有环，同时也找到了环的入口。 方法二：快慢指针法 算法思想：一个指针走两步；一个指针走一步；如果存在环，两个指针最终会指向同一个元素；如果不存在环，走两步的会最终走向空节点。 当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。 
确定有环后求环的长度 
通过公式的推导我们发现 L = k c − n L=kc-n L=kc−n（这里的 k k k 是倍数，有可能快指针在环里转了 k k k 圈），即相遇节点到入环点的距离等于链表的头到入环点的距离。写代码的时候只需要找到相遇节点，再让一个指针从头开始走即可。 2.8 判断两个链表是否相交1. 相交则求交点（链表不带环） 思路：若两个不带环的链表相交，则他们的尾节点必相同；若要求交点，则需要比较两个链表的长度，让较长的链表先向后遍历至和较短的链表长度相等，然后两个链表同时向后遍历，并比较节点是否相同，当遇到第一个相同的节点时，则为两个链表的交点。 2. 相交则求交点（链表可能带环） 情况分析： 若有两个链表，则他们的带环情况有以下三种可能： （1）两个链表都不带环 直接采用上述思路即可； （2）一个链表带环一个链表不带环 必定不想交； （3）两个链表都带环 下面详细讨论： 
当出现①情况时，两个链表不相交。当出现②情况时，两个链表的交点在环外，那么我们可以转化为不带环链表判断相交即可。当出现③情况时，两个链表的交点在环内，那么我们可以遍历其中一个链表的环，若在环内与另一个链表环的入口点相交，则两个链表相交，相遇点即为两个链表的交点。要判断为情况②还是情况③，只需判断两个链表环的入口点是否相同即可。
链表的 .next 指向问题 如果放在左边就表示是自己的指向，如果放在右边就表示是它的下一个节点。类似于代码中的这三行： node.next = head.next; head.next = head.next.next; node.next.next = head;这种就代表等号左边指向右边，左边的是指向，右边就代表确切的下一个节点。 如果类似于后两行代码： node = node.next.next; head = head.next;像这样，左边不带 .next 的是类似于赋值语句，自己的指针指向右边位置。 3 LeetCode
俗话说一图胜千言，接下来主要通过图片展示解决思路，通过代码展示实现的细节。 3.1 删除结点 3.1.1 题解方法1. 画草图： 理解指针的变动与思考逻辑！！(重要！实用！) 2. 边界条件： 怎么处理不会有空指针异常？在循环里放什么停止条件 如果是遍历链表元素，while(node!=null)如果是删除某个元素，需要，while(node.next!=null)需要考虑的仅仅是被改变 next 指针的部分，并且循环之后哪个指针在最后的节点处，就判断谁 # 比如快慢指针，输出中间节点，slow 和 fast 的指针都在变，但是 fast 先指向链表尾巴，所以判断 fast # 同时每个判断 next.next 的都必须先判断，next，才能保证 奇偶链长 中不会出现空指针异常 while(fast.next!=null && fast.next.next!=null){ slow = slow.next; fast = fast.next.next; }3. 只要会删除头结点，都要进行 dummy虚指针，有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性 4. 特殊的需求可以考虑结合各种工具类，比如删除重复里面，利用HashSet，删除倒数第k个，利用栈LinkedList 1.3.2 可能出现的问题① NullPointerException，就是当前节点为空，我们还去操作它的 next； ② 输出不了结果，一定是指针移动出了问题 1.3.3 题库列表237. 删除链表中的节点 ====面试题 02.03. 删除中间节点 203. 移除链表元素（虚拟头结点） 83. 删除排序链表中的重复元素剑指 Offer 18. 删除链表的节点面试题 02.01. 移除重复节点82. 删除排序链表中的重复元素 II19. 删除链表的倒数第 N 个结点（双指针经典类型） 876. 链表的中间结点86. 分隔链表328. 奇偶链表237. 删除链表中的节点 题目描述：给你一个需要删除的节点 node，但无法访问 第一个节点 head。链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。 # 题目说 node 不是链表中最后一个结点，直接将当前节点的值改为next的值，next指向next.next，实现原地更新 class Solution: def deleteNode(self, node): node.val = node.next.val node.next = node.next.next203. 移除链表元素 题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 ① 如果删除的节点是中间的节点，则问题似乎非常简单： 选择要删除节点的前一个结点 prev。将 prev 的 next 设置为要删除结点的 next。② 当要删除的一个或多个节点位于链表的头部时，要另外处理 三种方法： 删除头结点时另做考虑（由于头结点没有前一个结点）添加一个虚拟头结点，删除头结点就不用另做考虑递归双指针法1. 对头结点单独考虑 class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: prev, cur = None, head while cur: if cur.val == val: # 找到指定元素 if prev: # 不是头结点 prev.next = cur.next # 将删除位置的前一个节点的next指向删除位置的后一个结点 else: # 如果第一个就是删除结点 head = cur.next # 将头指针指向头节点的后一个结点 else: prev = cur cur = cur.next return head
2. 添加一个虚拟头结点 class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy = ListNode(-1, head) # 创建虚结点 prev = dummy while prev and prev.next: if prev.next.val == val: prev.next = prev.next.next else: prev = prev.next return dummy.next
3. 递归 class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: if head == None: return head # 因为递归函数返回的是已经删除节点之后的头结点 # 所以直接接上在 head.next，最后就只剩下判断头结点是否与需要删除的值一致了 head.next = self.removeElements(head.next, val) if head.val == val: return head.next else: return head
83. 删除排序链表中的重复元素 题目描述：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: curr = head # 指针节点，这里不会删除头结点 while curr and curr.next: if curr.val == curr.next.val: # 如果两个结点元素值相同，则执行删除 curr.next = curr.next.next else: curr = curr.next return head
题目解法并不唯一，可以使用递归、双指针、虚拟头结点、栈的方法，详细了解可以阅读：删除排序链表中的重复元素（五种方法） 剑指 Offer 18. 删除链表的节点 题目描述：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点 class Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: if head.val == val: # 如果头指针相等，直接返回 return head.next prev, cur = head, head.next # 双指针 while (cur and cur.val != val): # 找元素 prev, cur = cur, cur.next if cur: # 找到了，进行删除 prev.next = cur.next return head温馨提示： 这里既可以添加虚拟头结点，也可以先判断第一个结点是否满足条件，第二种方法更快，这里就采用先判断再循环的方式。 
面试题 02.01. 移除重复节点 题目描述：移除未排序链表中的重复节点。保留最开始出现的节点，由于未排序，重复的元素不一定连续。 class Solution: def removeDuplicateNodes(self, head: ListNode) -> ListNode: pre, cur = None, head # 初始化 pre, cur 节点引用（指针） visited = set() # 初始化 set 用于保存节点值 while cur: # 遍历链表 if cur.val in visited: # 若节点值 cur.val 在 set 中 pre.next = cur.next # 删除节点 cur else: # 若节点值 cur.val 不在 set 中 visited.add(cur.val) # 将 cur.val 添加进 set pre = cur # 令 pre 指向 cur ，作为下一轮的前驱节点 cur = cur.next # 遍历下一节点 return head # 删除完成，返回链表头节点 head
82. 删除排序链表中的重复元素 II 题目描述：给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: '''双指针记录 pre 用 cur 记录相同的数，加虚头节点''' dummy = ListNode(-1, head) prev, curr = dummy, dummy.next while curr and curr.next: if curr.val == curr.next.val: while curr and curr.next and curr.val == curr.next.val: # 如果有奇数个相同的值，就删不完，所以必须用 while 循环 curr = curr.next # 找到最后一个相等的数 curr = curr.next prev.next = curr else: prev = curr curr = curr.next return dummy.next
19、删除链表的倒数第 N 个结点 题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 1. 快慢指针 class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: if head == None: return head.next dummy = ListNode(-1, head) fast = dummy.next for _ in range(n): # 快指针先走n步 fast = fast.next slow = dummy while fast: # 快慢指针同时走，直到 fast 指针到达尾部节点，此时 slow 到达倒数第 N 个节点的前一个节点 fast, slow = fast.next, slow.next slow.next = slow.next.next # 删除节点，并重新连接 return dummy.next
2. 循环迭代 – 找到 length -n 个节点 class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0, head) cur, length = head, 0 # step1: 获取链表长度 while cur: length += 1 cur = cur.next cur = dummy # step2: 找到倒数第N个节点的前面一个节点 for _ in range(length - n): cur = cur.next cur.next = cur.next.next # step3: 删除节点，并重新连接 return dummy.next3. 递归迭代 – 回溯时，进行节点计数 class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: if not head: self.count = 0 return head head.next = self.removeNthFromEnd(head.next, n) # 递归调用 self.count += 1 # 回溯时进行节点计数 return head.next if self.count == n else head876、链表的中间结点 题目描述：给你单链表的头结点 head ，请你找出并返回链表的中间结点。 （1）若为奇数，指向中间的结点，若为偶数，指向中间靠后的结点 class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow, fast = head, head while fast and fast.next: # 如果不加 fast，链表元素个数为偶数时会报空指针异常； slow = slow.next fast = fast.next.next return slow
（2）若为奇数，指向中间的结点，若为偶数，指向中间靠前的结点 class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow, fast = head, head while fast.next is not None and fast.next.next is not None: fast = fast.next.next slow = slow.next return slow
86、分隔链表（两个临时链表） 题目描述：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。 class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: dummy1, dummy2 = ListNode(-1), ListNode(-1) # dummy1 存放小于x链表的虚拟头结点，dummy2存放不小于x的虚拟头结点 p, p1, p2 = head, dummy1, dummy2 # p 负责遍历链表，类似合并两个有序链表的逻辑；p1, p2 指针负责生成结果链表 while p: if p.val 2-->2-->4-->3-->5-->2|-->4-->3-->5-->2|-->4-->...，看出来了吗？形成了一个环了！
因此在每步的赋值结束后，应当对next清除，以防止在最后的时候陷入这种无限循环。 # 断开原链表中的每个结点的 next 指针 temp = p.next p.next = None p = temp或者，如果不想每个都断开，其实在 p 往下走的时候，每个 p1 和 p2 的 next 都在同时进行着更新，因此只有 p2 的最后一个是存在问题的，因此也可以加一句 p2.next = None 来解决。 class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: # dummy1 存放小于x链表的虚拟头结点， 度没有 存放不小于x的虚拟头结点 dummy1, dummy2 = ListNode(-1), ListNode(-1) # p1, p2 指针负责生成结果链表 p1, p2 = dummy1, dummy2 # p 负责遍历链表，类似合并两个有序链表的逻辑 # 这里是将两个链表分解成两个链表 p = head while p: if p.val Optional[ListNode]: dummy1, dummy2 = ListNode(-1), ListNode(-1) p, p1, p2 = head, dummy1, dummy2 count = 0 while p: if count % 2 == 0: p1.next = p p1 = p1.next else: p2.next = p p2 = p2.next count += 1 temp = p.next p.next = None p = temp p1.next = dummy2.next return dummy1.next
3.2 反转链表
3.2.1 题库列表
206. 反转链表====剑指 Offer 24. 反转链表 92. 反转链表 II 234. 回文链表====面试题 02.06. 回文链表 25. K 个一组翻转链表 206、反转链表 题目描述：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 1. 双指针法迭代 class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev, cur = None, head # 申请两个节点，pre和 cur，pre指向None while cur: # 遍历链表 temp = cur.next # 记录当前节点的下一个节点 cur.next = prev # 然后将当前节点指向pre prev = cur # pre和cur节点都前进一位 cur = temp return prev
2. 尾递归法 class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if head == None or head.next == None: return head # reverse_head 表示 head.next 后面一整段反转之后的头结点，所以最后return reverse_head reverse_head = self.reverseList(head.next) head.next.next = head # 此时 head.next 指向的已经是反转部分的尾巴 head.next = None # head 指向 None，表示此时 head 已经是尾巴了 return reverse_head
92. 反转链表 II 题目描述：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left Optional[ListNode]:
if head.next == None:
return head
dummy = ListNode(-1, head)
prev = dummy
for _ in range(left-1): # 迭代法，先找到起点
prev= prev.next # 来到 left 节点的前一个节点
curr = prev.next # cur 是真正反转的指针
tail = curr
for _ in range(right-left+1):
node = curr.next # node 保存 curr.next 的临时指针，保存后面的顺序
curr.next = prev.next # 将要反转的节点，接入到 left 节点
prev.next = curr
tail.next = node
curr = node
return dummy.next
234. 回文链表 题目描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 1. 数组模拟 class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: prev, val_list = head, [] while prev: val_list.append(prev.val) prev = prev.next return val_list == val_list[::-1]2. 维持半条翻转链表（双指针） class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: p, slow, fast = head, head, head # p 存储前半段的尾结点 while fast and fast.next: # 快慢指针找到中间节点 p = slow slow = slow.next fast = fast.next.next left, right = head, self.reverse_list(slow) # 额外维持的半条链表；反转 slow 后面的元素 q = right # 存储末尾的断点用于恢复原来链表的顺序 while right: # 两个半长链表的比较 遍历两个 半长链表 if left.val != right.val: return False left = left.next right = right.next p.next = self.reverse_list(q) # 还原链表 return True def reverse_list(self, head: Optional[ListNode]): prev, curr = None, head while curr: node = curr.next curr.next = prev prev = curr curr = node return prev温馨提示： 比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。可以记录前半段的尾结点，将后半部分翻转之后在比较完成之后再次翻转，再让前半段的尾结点指向两次翻转的后半部分即可还原链表。 
25. K 个一组翻转链表 题目描述：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 1. 模拟法 class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if k== 1 or not head or not head.next: return head dummy = ListNode(0, head) prev1, prev2, curr = dummy, dummy, dummy.next count = -1 while prev1: # 查找节点个数 count += 1 prev1 = prev1.next tail = curr for i in range(count//k): # K个一组反转 if i != 0: prev2 = tail tail = curr for _ in range(k): temp = curr.next curr.next = prev2.next prev2.next = curr tail.next = temp curr = temp return dummy.next
3.3 合并链表
3.3.1 题库列表
21. 合并两个有序链表 23. 合并K个升序链表 21. 合并两个有序链表 题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: prehead = ListNode(-1) # 哨兵节点 prev = prehead # 指针节点 while list1 and list2: if list1.val Optional[ListNode]: if not lists: return None head = lists[0] for item in lists[1:]: head = self.mergeTwoLists(head, item) return head def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: prehead = ListNode(-1) # 哨兵节点 prev = prehead # 指针节点 while list1 and list2: if list1.val ListNode: if not lists: return None n = len(lists) # 记录子链表数量 return self.mergeSort(lists, 0, n - 1) # 调用归并排序函数 def mergeSort(self, lists: List[ListNode], l: int, r: int) -> ListNode: if l == r: return lists[l] m = (l + r) // 2 L = self.mergeSort(lists, l, m) # 循环的递归部分 R = self.mergeSort(lists, m + 1, r) return self.mergeTwoLists(L, R) # 调用两链表合并函数 def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: prehead = ListNode(-1) # 哨兵节点 prev = prehead # 指针节点 while list1 and list2: if list1.val Optional[ListNode]: dummy = ListNode(-1, head) # 会移动头结点，这里虚拟头结点 last_sorted, curr = head, head.next # last_sorted 维护已排序部分的最后一个位置；curr 为遍历的待插入元素 while curr: # 外层循环遍历完链表所有数；内层循环遍历[head, lastSort]这段位置找插入 if curr.val >= last_sorted.val: last_sorted = last_sorted.next # 大，直接后移，或者直接 last_sorted = cur else: prev = dummy # 用来遍历已经排序的部分 while prev.next.val Optional[ListNode]: if not head: # 空链表直接返回 return head length = 0 # 获取链表的长度 node = head while node: length += 1 node = node.next dummy_head = ListNode(0, head) sub_length = 1 # 归并的有效处理长度，最小为 1 while sub_length bool: if not head or not head.next: return False slow, fast = head, head while fast and fast.next: # 快指针在前面，所以只要判断快指针是否达到了队尾就可以 fast = fast.next.next slow = slow.next if slow == fast: return True return False
142. 环形链表 II 题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。 class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return None slow, fast = head, head while fast and fast.next: # 快慢指针找重合点 fast = fast.next.next slow = slow.next if slow == fast: # 重合了，这个时候，从头来一个指针遍历 p1 = slow p2 = head while p1 != p2: p1 = p1.next p2 = p2.next return p2 return None # 没有环，返回 None
终于小结完了，期待下一专题——二叉树，也期待各位小伙伴们一起来学习与交流！ 
参考
一文搞定常见的链表问题：https://leetcode.cn/problems/linked-list-cycle/链表常见问题解决思路：https://blog.csdn.net/weixin_43910851/article/details/105725577一文通数据结构与算法之——链表+常见题型与解题策略+Leetcode经典题：https://blog.csdn.net/qq_42647903/article/details/120594925两个技巧搞定常见面试链表题：https://blog.csdn.net/weixin_45750855/article/details/算法面试题 | 链表问题总结：https://juejin.cn/post/6882370280946302983
|
【本文地址】