赤峰网站建设哪个服务好,wordpress 数据库ip,南阳高端网站建设,wordpress app 管理前言#xff1a;只照着常考题去刷题确实是一种方法。但调研之后发现自己还是考虑不周#xff0c;刷题刷的不应该是题#xff0c;而是解题的思路和熟练程度。于是我决定重新组织一下刷题笔记的讲解顺序#xff0c;不再以面试常考题来刷。而是以面试出题频率#xff0c;方法…前言只照着常考题去刷题确实是一种方法。但调研之后发现自己还是考虑不周刷题刷的不应该是题而是解题的思路和熟练程度。于是我决定重新组织一下刷题笔记的讲解顺序不再以面试常考题来刷。而是以面试出题频率方法思路类型和难度等要素来综合排序。每一次分享我们会沿着一个主题展开它的各种变体确保一次性能吃透与它类似的题目。往后我们会确定主题对该主题下问题一步步分解然后确定模板、举一反三去做题。而不是简单无脑地刷题。这一次我们的主题是链表。本文会覆盖以下三个内容Leetcode 中文上所有链表题的题型和难易分布一览链表题的大致考察点常规解题思路和技巧题海将解题模板熟练化一、面试常考链表题调研首先我们点进 Leetcode 页面依次点题库标签链表出现频率便可以看到以下的题目排序。我们可以发现链表类题目相对都是比较容易简单中等题五五开很少有困难题目。所以它这里更多的是考察一个代码的熟练度。比如对边界的处理对指针的操作等。Leetcode 链表leetcode-cn.com二、链表常见考察点链表和数组统称为线性表。数组所有元素都储存在一段连续的内存中具有通过下标访问数据的能力 O(1)。但这也让它扩容和删除元素的成本变得很高 O(n)。因为扩容要新申请一块更大的内存复制所有元素再删除原来的内存。而删除插入元素需要把该元素位置之后的其它元素都往前或往后挪一个位置若插入时刚好分配的内存满了还要重新进行扩容操作。对比之下链表由多个结点组成每个结点包含了数据和指针。数据指向具体的内存块而指针指向一个结点的内存地址。一般链表用一个 head 头结点指针来表示。链表的好处是插入删除的空间复杂度是 O(1)但是访问某个结点的空间复杂度是 O(n)。设计链表class ListNode:def __init__(self, x):self.val xself.next Noneclass MyLinkedList:def __init__(self):Initialize your data structure here.self.head Noneself.length 0def print(self):node self.headwhile node:print(node.val, end )node node.nextprint()def get(self, index: int) - int:Get the value of the index-th node in the linked list. If the index is invalid, return -1.if index self.length:return -1prev self.headcurr self.headfor _ in range(index):prev currcurr curr.nextreturn curr.valdef addAtHead(self, val: int) - None:Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.self.length 1if not self.head:self.head ListNode(val)else:new_head ListNode(val)new_head.next self.headself.head new_headdef addAtTail(self, val: int) - None:Append a node of value val to the last element of the linked list.self.length 1if not self.head:self.head ListNode(val)else:tail self.headwhile tail.next:tail tail.nexttail.next ListNode(val)def addAtIndex(self, index: int, val: int) - None:Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.if index self.length:returnif index 0:new ListNode(val)new.next self.headself.head newself.length 1returnif index self.length:self.addAtTail(val)returnprev self.headcurr self.headfor _ in range(index):prev currcurr curr.nextprev.next ListNode(val)prev prev.nextprev.next currself.length 1def deleteAtIndex(self, index: int) - None:Delete the index-th node in the linked list, if the index is valid.if index self.length:self.length - 1if index 0:prev self.headself.head self.head.nextprev.next Nonedel prevreturnprev self.headcurr self.headfor _ in range(index):prev currcurr curr.nextprev.next curr.nextcurr.next Nonedel curr1. 节点的返回 全 8 道题题目一般要你返回链表中满足某个条件的节点大都可以使用双指针的思想。返回倒数第 k 个节点的值 倒数第 k 个节点意味着某个指针要再走 k 步才会到结尾。怎样知道一个结点它的位置距离尾部有 k 步呢我们可以用两个指针beforeafter 分别指向头结点。其中 before 结点不动after 结点走 k 步后才让 before 结点开始往后走。二者的步伐都一致二者就会相隔 k 步。当 after 结点走到结尾的时候before 结点所在的位置刚好是要返回的结点。代码如下# Definition for singly-linked list.
链表中倒数第 k 个节点往后的链表该题与上一题无差别只是返回的内容是指针而不是值。这里要注意一下以防 k 过大溢出 k 的取值要与链表的长度取膜。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) - ListNode:n 0node headwhile node:node node.nextn 1k k % (n1)if n 2:return headbefore after headfor i in range(k):after after.nextwhile after:after after.nextbefore before.nextreturn before链表的中间结点这里同样是两个指针不过是一快一慢。快指针每次走两步慢指针每次走一步。两个指针同时从 head 开始走。如果链表长度为奇数中点节点两边节点个数相等最终快指针的下一个为空时停止直接返回慢指针。如果链表长度为偶数则没有中间节点能平分链表我们取右边的最左边节点作为返回即此时快指针为空时返回慢指针。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def middleNode(self, head: ListNode) - ListNode:if not head:return headfast, slow head, headwhile fast and fast.next:fast fast.next.nextslow slow.nextreturn slow环形链表也是双指针。我们考虑让快指针比慢指针的步伐快走一步即快指针每次走两步慢指针每次走一步。这样快指针会先进入环中当慢指针叶进入环后与快指针刚好相差 k 个结点设 n1 为环外的结点个数n2 为构成环的结点个数则很容易得到 n2 - n1 k。当它们继续在环中一快一慢的步伐一直前行由于每次快指针都能追上慢指针一个结点所以它们之间的差距每次迭代都会小一步即 k 会越来越小。直到 k 0 时二者相遇说明有环。反过来想若快指针能走到一个尽头即它走到的位置下一个结点为空则说明没有环。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: ListNode) - ListNode:slow, fast head, headwhile 1:if not fast or not fast.next:return Falsefast, slow fast.next.next, slow.nextif fast slow:breakreturn True环形链表 Ⅱ如果我们要找入环点的位置根据前面的公式慢指针刚进入环中的时候满足 n2 - n1 k。若快指针降到每次一步的速度往前走 n2 - k 步则刚好获得 head 到入环口的结点个数 n1。第一次快慢指针相遇时慢指针走了 k n1 n2 步所以要返回入环口我们只需要在快慢指针相遇的时候让快慢指针再以每次一步的步频往前走直到二者第二次相遇。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: ListNode) - ListNode:slow, fast head, headwhile 1:if not (fast and fast.next):return Nonefast, slow fast.next.next, slow.nextif fast slow:breakslow headwhile fast ! slow:fast fast.nextslow slow.nextreturn slow两个链表的第一个公共节点链表相交公共结点有一个特征是它离尾部的距离是一样的。对于长链表 B 来说它要比短链表 A 事先多走 k 步才能到公共结点。这个 K 步刚好是链表 B 比 链表 A 多出来的长度。要怎样获得这个 K 呢一种简单方法是分别算两个链表的长度相减便是。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:if not headA or not headB:return Nonedef get_length(head):n 0while head:head head.nextn 1return nA_length, B_length get_length(headA), get_length(headB)if A_length B_length:headA, headB headB, headAfor _ in range(abs(A_length - B_length)):headA headA.nextwhile headA and headB and headA ! headB:headA headA.nextheadB headB.nextif not headA or not headB:return Nonereturn headA一般人很少会想到这题也可以用快慢指针来做。一开始从两个链表以1的步伐分别各走一个指针。当其中一个先到达尾部时让它下一步往后跳到另一个链表的头结点继续走当另一个指针走到尾部时同理。最终当它们第一次重叠时返回的便是最开头的公共节点。问题是我们要如何判断它没有公共交点呢也简单。当其中一个节点能够两次走到结尾则说明没有公共交点。我们设立两个 Bool 变量去分别记录两个指针是否走过结尾。若走过就返回 None。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:if not headA or not headB:return Nonep1, p2 headA, headBp1_first_None, p2_first_None False, Falsewhile p1 ! p2:p1, p2 p1.next, p2.nextif not p1:if p1_first_None:return Nonep1 headBp1_first_None Trueif not p2:if p2_first_None:return Nonep2 headAp2_first_None Truereturn p12. 节点的删除 全 9 道题Leetcode 还会考核满足某一条件的节点的删除。如上图所示。节点删除考察的是要如何改变链表的指针域以达到删除的目的。删除链表中的节点只给要删除节点删除中间节点我们先从最简单的来。一种删除节点的题是它不给你链表只给你某个要删除当前节点。最直接的方法是把当前节点的下一个节点的值复制到当前节点上然后再将当前节点连接到它的下下个节点。从内存上看它删掉的是当前节点的下一个节点。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def deleteNode(self, node)::type node: ListNode:rtype: void Do not return anything, modify node in-place instead.node.val node.next.valnode.next node.next.next删除链表中的节点给了整个链表保证不重复另一种要删除的是其内存。前面那种复制的方法就不行了。这种题一般会给你整个链表的头节点。考虑到我们可能会删掉头节点。我们会用创建一个连向头节点的虚拟节点的方式来解。当你熟悉了这一技巧往后的变体就都大同小异。无疑是改变了一下要删除节点的条件。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next None
class Solution:def deleteNode(self, head: ListNode, val: int) - ListNode:dummy ListNode(float(inf))dummy.next headnode dummywhile node.next and node.next.val ! val:node node.nextnode.next node.next.nextreturn dummy.next删除链表中的节点给了整个链表可能会重复# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def removeElements(self, head: ListNode, val: int) - ListNode:dummy ListNode(float(inf))dummy.next headnode dummywhile node.next:if node.next.val val:node.next node.next.nextelse:node node.nextreturn dummy.next删除链表的倒数第N个节点这题结合了之前的双指针找倒数第K个节点的思路先让快指针先走 n1 步再一起走到结尾则慢指针刚好位于倒数第 n1 个节点。这时执行删除操作。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:dummy ListNode(0)dummy.next headfirst, second dummy, dummyfor i in range(n1):first first.nextwhile first:first first.nextsecond second.nextsecond.next second.next.nextreturn dummy.next这往后的变体还可以是删除链表 N 到 M个节点。删除链表第M个节点后的 N 个节点。等等。方法都大同小异。用双指针找位置用 dummy 虚拟节点避免删除头。删除重复节点 I你可以看到这段代码和上面代码唯一的区别就是判定条件那里改动了一下。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def deleteDuplicates(self, head: ListNode) - ListNode:dummy ListNode(float(inf))dummy.next headnode dummywhile node.next:if node.val node.next.val:node.next node.next.nextelse:node node.nextreturn dummy.next删除重复节点 Ⅱ (不包含重复节点)当我们要把重复节点全部去掉时需要额外一个指针 pre 来作为辅助。如果存在两个值相同的节点当前指针 curr 就会一直往后走直到跑到一个与该值不同的节点位置。让pre .next cur 完成节点的删除。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def deleteDuplicates(self, head: ListNode) - ListNode:dummy ListNode(float(inf))dummy.next headcur dummywhile cur:pre curcur cur.nextwhile cur and cur.next and cur.val cur.next.val:val cur.valwhile cur and cur.val val:cur cur.nextpre.next curreturn dummy.next删除重复节点 Ⅲ (未排序链表)链表单调递增时能保证前面操作了某个值的删除后后面不会再操作与之一样的删除。但单调性不能保证时原来的思路就不能照搬了。这时有两种做法。一种是用哈希表储存重复过的数值。时间和空间复杂的都为 O(n)。另一种是两遍循环操作时间复杂度为 O(n²)空间复杂度为 O(1)class Solution:def removeDuplicateNodes(self, head: ListNode) - ListNode:if not head:return headoccurred set()occurred.add(head.val)pre headwhile pre.next:cur pre.nextif cur.val not in occurred:occurred.add(cur.val)pre pre.nextelse:pre.next pre.next.nextreturn headclass Solution {
public:ListNode* removeDuplicateNodes(ListNode* head) {ListNode* p1 head;while (node) {ListNode* p2 p1 ;while (p2-next) {if (p2-next-val p1-val) {p2-next p2-next-next;} else {p2 p2-next;}}p1 p1-next;}return head;}
};从链表中删去总和值为零的连续节点这道题我们可以用前缀数组来解。第一遍遍历时我们用一个字典储存前 k 个节点和 - 第k个节点的 pair。第二遍遍历时我们把当前节点的下一个都赋值为前缀字典中最后储存的节点。举个例子说head [1,2,-3,3,1]前缀字典每次变化sum 操作0 {0: dummy}1 {0: dummy, 1: node[0]}3 {0: dummy, 1: node[0], 3: node[1]}0 {0: node[2], 1: node[0], 3: node[1]}3 {0: node[2], 1: node[0], 3: node[3]}4 {0: node[2], 1: node[0], 3: node[3], 4: node[4]}第二次遍历链表变化sum 操作0 dummy - node[3]1 node[0]- node[1]3 node[1] - node[4]0 node[2] - node[3]3 node[3] - node[4]4 node[4] - None汇总后最终虚拟节点之后接的为dummy - node[3] - node[4] - None# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def removeZeroSumSublists(self, head: ListNode) - ListNode:hash_map dict()dummy ListNode(0)dummy.next headnode dummycurr_sum 0while node:curr_sum node.valhash_map[curr_sum] nodenode node.nextnode dummycurr_sum 0while node:curr_sum node.valnode.next hash_map[curr_sum].nextnode node.nextreturn dummy.next3. 节点的求和 全 4 道题这里主要用的是节点直接位置和值的关系。二进制链表转整数直接每进一位把之前的结果乘上2再加上当前节点的值便可class Solution:def getDecimalValue(self, head: ListNode) - int:res 0node headwhile node:res res*2 node.val;node node.nextreturn res两数相加该题与我们小学学加法竖式计算是一样的。从低位到高位用一个中间变量存进位。 Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode:dummy ListNode(0)p1, p2, cur l1, l2, dummyoverflow 0while p1 or p2:x p1.val if p1 else 0y p2.val if p2 else 0curr_sum overflow x yoverflow curr_sum // 10cur.next ListNode( curr_sum % 10)cur cur.nextif p1:p1 p1.nextif p2:p2 p2.nextif overflow 0:cur.next ListNode(overflow)return dummy.next两数相加 II如果我们要反过来相加则需要借助栈这个数据结构。class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode:s1, s2 [], []while l1:s1.append(l1.val)l1 l1.nextwhile l2:s2.append(l2.val)l2 l2.nextres Noneoverflow 0while s1 or s2 or overflow ! 0:p1_val 0 if not s1 else s1.pop()p2_val 0 if not s2 else s2.pop()curr_sum p1_val p2_val overflowoverflow curr_sum // 10curr_sum % 10cur ListNode(curr_sum)cur.next resres curreturn res链表求和上面一题如果不使用额外空间要怎么做呢方式是我们用其中一个链表作为临时变量存我们当前位的临时结果。class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode:dummy ListNode(-1)cur dummyoverflow 0while l1 and l2:curr_sum l1.val l2.val overflowl1.val curr_sum % 10overflow curr_sum // 10cur.next l1cur cur.nextl1, l2 l1.next, l2.nextleft Noneif l1:leftl1else:leftl2while left and overflow 0:curr_sum left.val overflowleft.val curr_sum % 10overflow curr_sum // 10cur.next leftcur cur.nextleft left.nextif overflow 0:cur.next ListNode(overflow)return dummy.next4. 节点的位置调整 全 11 题这类题目通常需要我们用多个指针根据题目条件控制某个节点前中后三个位置的转换。反转链表# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def reverseList(self, head: ListNode) - ListNode:prev Nonecurr headwhile curr:next_ curr.nextcurr.next prevprev currcurr next_return prev该题也有递归的解法class Solution(object):def reverseList(self, head)::type head: ListNode:rtype: ListNodeif not head or not head.next:return headcur self.reverseList(head.next)head.next.next headhead.next Nonereturn cur反转链表 II 指定m到n反转比上题多两个步骤一个是先走m-1步找到要反转的链表部分的起点的前一个节点A另一个是用上述算法反转 n-m 次后让A的下一个连到反转后的链表反转后的链表的头连到第n个节点。class Solution:def reverseBetween(self, head: ListNode, m: int, n: int) - ListNode:dummy ListNode(0)dummy.next headA dummyfor i in range(m-1):A A.nextprev Nonecurr A.nextB A.nextfor i in range(n-m1):next_ curr.nextcurr.next prevprev currcurr next_A.next prevB.next next_return dummy.next递归法class Solution(object):def reverseBetween(self, head, m, n)::type head: ListNode:type m: int:type n: int:rtype: ListNodedef reverseN(head,n):if n 1:return head# 以 head.next 为起点需要反转前 n - 1 个节点last reverseN(head.next, n-1)successor head.next.next # 以head.next为开头的链表已经完成翻转那么head.next.next正确指向后继节点head.next.next headhead.next successorreturn lastif m 1: return reverseN(head,n)head.next self.reverseBetween(head.next,m-1,n-1)return head回文链表当你熟悉了如何翻转链表你还可以用它来检查回文。首先我们用快慢指针的方式找到中点。然后对中点往后部分翻转链表。再看看翻转的后半部分和前半部分是否相等。class 两两交换链表中的节点交换两个节点的技巧之前在反转链表中写过。这里可以照用。不同在我们每次反转局部的两个节点后往后要把 prev 移动到当前的第一个节点上。class Solution:def swapPairs(self, head: ListNode) - ListNode:if not head or not head.next:return headdummy ListNode(0)dummy.next headprev dummywhile prev.next and prev.next.next:first prev.nextsecond prev.next.nextprev.next secondfirst.next second.nextsecond.next firstprev firstreturn dummy.next奇偶链表class Solution:def oddEvenList(self, head: ListNode) - ListNode:if not head:return headodd, even head, head.nextoddHead, evenHead odd, evenwhile even and even.next:odd.next even.nextodd odd.nexteven.next odd.nexteven even.nextodd.next evenHeadreturn oddHead旋转链表这道题我们可以用返回倒数第k个节点的双指针方法找到旋转链表的新头然后将结尾给连上旧头让新头与前面的节点断开返回新头就完成了旋转。class Solution:def rotateRight(self, head: ListNode, k: int) - ListNode:if not head or not head.next:return headnode headn 0while node:node node.nextn 1k k % nif not k:return headfast, slow head, headfor _ in range(k-1):fast fast.nextslow_prev Nonewhile fast.next:slow_prev slowslow slow.nextfast fast.nextfast.next headslow_prev.next Nonereturn slow排序链表比起 array 版本不同的是我们要用 next 来做 i 的位移操作。空节点或单节点作为递归条件返回。一开始创建三个空节点leftmidright并用对应的新指针 left_tail, mid_tail, right_tail 分别指向它们。接着我们遍历链表对于当前节点值比头节点小的就放在 left_tail 后面若等于就放在 mid_tail 后面若小于则放在 right_tail 后面。每次插入完要后移其坐标。遍历完后我们把结尾都归 None。然后开始递归调用快排。把mid部分的快排结果放在链表 left 的右边把 right 的快排结果放在链表 mid 的右边。最后返回的是虚拟节点 left 右边的节点为最终排序好的整个链表。代码如下class Solution:def get_tail(self, head):while head.next: head head.nextreturn headdef sortList(self, head: ListNode) - ListNode:if not head or not head.next:return headleft, mid, right ListNode(-1), ListNode(-1), ListNode(-1)left_tail, mid_tail, right_tail left, mid, rightval head.valp headwhile p:if p.val val:left_tail.next pleft_tail left_tail.nextelif p.val val:mid_tail.next pmid_tail mid_tail.nextelse:right_tail.next pright_tail right_tail.nextp p.nextleft_tail.next mid_tail.next right_tail.next Noneleft.next self.sortList(left.next)right.next self.sortList(right.next)self.get_tail(left).next mid.nextself.get_tail(mid.next).next right.nextres left.nextreturn res从尾到头打印链表使用栈先把遍历链表把节点值放进栈再一个个出栈。class Solution:def reversePrint(self, head: ListNode) - List[int]:stk []node headwhile node:stk.append(node.val)node node.nextres []while stk:res.append(stk.pop())return res重排链表这道可以结合之前题的技巧把问题分解成三步。第一步用双指针方法找到中点节点。第二步用反转链表方法把后半段反转。第三步合并两个链表。class Solution:def reverseList(self, head: ListNode) - ListNode:prev Nonecurr headwhile curr:next_ curr.nextcurr.next prevprev currcurr next_return prevdef 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, headslow_prev Nonewhile fast and fast.next:fast fast.next.nextslow_prev slowslow slow.next# 中点后面的部分翻转链表slow_prev.next Nonereversed_right self.reverseList(slow)# 合并两个链表first, second head, reversed_rightwhile first and second:first_next, second_next first.next, second.nextfirst.next, second.next second, first_nextif not first_next and second_next:second.next second_nextbreakfirst, second first_next, second_nextreturn head对链表进行插入排序如动图所示每次取出一个节点 curr去和最开始的节点往后一个个比较如果发现它小于当前节点就继续右移直到它大于等于当前节点则执行插入操作。class Solution:def insertionSortList(self, head: ListNode) - ListNode:if not head or not head.next:return headdummy ListNode(float(-inf))dummy.next headprev dummycurr dummy.nextwhile curr:if curr.val prev.val:tmp dummywhile tmp.next.val curr.val:tmp tmp.nextprev.next curr.nextcurr.next tmp.nexttmp.next currcurr prev.nextelse:prev, curr prev.next, curr.nextreturn dummy.nextK 个一组翻转链表这道题的难点是需要常数空间。我们可以先写好一个反转链表。然后用三个指针 lastHead, currHead, nextHead 来分别表示要反转链表的上一个尾节点头节点以及下一个要反转的链表的头节点。迭代时部分反转链表再补连上。class Solution:def reverse(self, head):prev Nonecurr headwhile curr:next_ curr.nextcurr.next prevprev currcurr next_return prevdef reverseKGroup(self, head: ListNode, k: int) - ListNode:dummy ListNode(0)dummy.next headnode dummylast_head dummycurr_head node.nextto_end Falsewhile node:for _ in range(k):node node.nextif not node:to_end Truebreakif to_end:breaknext_head node.nextnode.next Nonereversed_head self.reverse(curr_head)last_head.next reversed_headlast_head curr_headcurr_head.next next_headnode curr_headcurr_head next_headreturn dummy.next5. 链表的分割 全 2 道题分隔链表左右两边各设置一个虚拟指针一个用来接小于x的数一个用来接大于等于x的数最后再把两段接起来返回。class Solution:def partition(self, head: ListNode, x: int) - ListNode:dummy_left, dummy_right ListNode(float(-inf)), ListNode(float(inf))left, right dummy_left, dummy_rightcurr headwhile curr:if curr.val x:left.next currleft left.nextelse:right.next currright right.nextcurr curr.nextleft.next dummy_right.nextright.next Nonereturn dummy_left.next分隔链表这道题就有点偏技巧性需要先用余数预估长的有多少段短的有多少段。class Solution:def splitListToParts(self, root: ListNode, k: int) - List[ListNode]:n 0node rootwhile node:n 1node node.nextnode rootout []remain n % kshort_size n // k long_size short_size 1for i in range(k):out.append(node)if remain 0:size long_sizeelse:size short_sizenext_head nodetail Nonefor _ in range(size):tail next_headnext_head next_head.nextif tail:tail.next Nonenode next_headremain - 1return out6. 链表的合并 全 2 道两个有序链表合并看代码比较简单。需要用到虚拟节点 dummy 的技巧。合并两个有序链表class Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode:dummy ListNode(0)node dummywhile l1 and l2:if l1.val l2.val:node.next l1node, l1 node.next, l1.nextelse:node.next l2node, l2 node.next, l2.nextif l1:node.next l1else:node.next l2return dummy.next
合并K个排序链表这其实就是搜索引擎中的 MERGE 算法的变体。倒排索引中每一个词项会对应一个包含该词项的文章ID是一个长长的链表。我们如何把匹配到超过2个以上关键词的篇章合并实际会用到跳表去优化。但这道题相对简单只需要输出合并后的排序序列便可。核心思想和合并2个排序链表一致但不同在我们需要维持一个最大容量为k的 buffer 来存放当前的中间节点值。我们可以用一个 heap 用来对 buffer 中的节点进行排序。每次出一个值最小的节点放在要合并的链表的后面。时间复杂度为 O(nlogk)空间复杂度为 O(k)class 7. 链表的复制 就 1 道复杂链表的复制复制带随机指针的链表剑指 Offer 经典题目。先每个一个节点插入一个 node然后利用 节点的下一个节点的随机节点等于节点的随机节点的下一个节点特性来完成中间插入 node 的随机节点连接的复制。最后再两两拆分便复制完成。
# Definition for a Node.
class Node:def __init__(self, x: int, next: Node None, random: Node None):self.val int(x)self.next nextself.random randomclass Solution:def copyRandomList(self, head: Node) - Node:if not head:return headp headwhile p:node Node(p.val)next_ p.nextp.next, node.next node, next_p next_p headwhile p:if p.random:p.next.random p.random.nextp p.next.nextdummy Node(0)dummy.next headp1, p2 dummy, head while p1 and p2:p1.next p2.nextp1 p1.nextp2.next p1.nextp2 p2.nextreturn dummy.next8. 与其它数据结构交叉 全部 5 道二叉树中的列表 与二叉树的 subTree 一样解法上我们需要些一个dfs一旦存在当前链表节点和树节点的值不匹配就返回 False。否则继续往下遍历找节点。时间复杂度 空间复杂度为函数栈的调用检查链表长度不会超过树的高度因为超过就会返回 False所以是 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next None# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def isSubPath(self, head: ListNode, root: TreeNode) - bool:if not root:return Falseif not head:return Truedef dfs(head, root):if not head:return Trueif not root:return Falseif root.val ! head.val:return Falsereturn dfs(head.next, root.left) or dfs(head.next, root.right)return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)有序链表转换二叉搜索树 与二叉树相关思路是用中序遍历是顺序的。构建二叉树时用中序遍历每次节点就刚刚好与生成的树对齐。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next None# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def sortedListToBST(self, head)::type head: ListNode:rtype: TreeNodenode headn 0while node:node node.nextn 1def dfs(l, r):nonlocal headif l r:return Nonemid (l r) // 2left dfs(l, mid)root TreeNode(head.val)root.left left head head.nextroot.right dfs(mid1, r)return rootreturn dfs(0, n)扁平化多级双向链表 与 bfsdfs 相关
# Definition for a Node.
class Node:def __init__(self, val, prev, next, child):self.val valself.prev prevself.next nextself.child child
class Solution:def flatten(self, head: Node) - Node:if not head:return Nonedummy Node(0, None, head, None)prev dummystk [head]while stk:curr stk.pop()prev.next currcurr.prev previf curr.next:stk.append(curr.next)if curr.child:stk.append(curr.child)curr.child Noneprev currdummy.next.prev Nonereturn dummy.next
链表组件 使用 Set 作为去重技巧class Solution(object):def numComponents(self, head, G):Gset set(G)curr headans 0while curr:if curr.val in Gset:if not curr.next or curr.next.val not in Gset:ans 1curr curr.nextreturn ans链表中的下一个更大节点 链表与单调栈class Solution:def nextLargerNodes(self, head: ListNode) - List[int]:node headstk []ans []i 0while node:ans.append(0)while stk and stk[-1][0].val node.val:ans[stk[-1][1]] node.valstk.pop()stk.append((node, i))i 1node node.nextreturn ans总结一共 45 道题刷了大概一周时间。一些常用的技巧不好用语言去总结而是更多看代码、自己去写才会明白。大部分链表的基本思路就是虚拟节点双指针。其中双指针用的最灵活。掌握了这几个技巧会发现很多题都是可以分解成几个基本题的原型去做。另外链表与其它数据结构的综合题涉及的都是其它知识。日后会再一一总结。但愿在正式秋招之前能总结完头部的专题。最后附上这一专题的脑图
