2026.3.1
相交链表
from typing import Optional:返回目标类型或None
一个链表为a+c，另一个链表为b+c。走完一个开始走另一个，最终两个指针都走a+b+c，并在相交点相遇。
from typing import Optional
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:if not headA or not headB:return NonepA, pB = headA, headBwhile pA != pB:pA = pA.next if pA else headBpB = pB.next if pB else headAreturn pAdef create_linked_list(arr):if not arr:return Nonehead = ListNode(arr[0])cur = headfor val in arr[1:]:cur.next = ListNode(val)cur = cur.nextreturn heada=[4,1,8,4,5]
b=[5,6,1,8,4,5]
# 注意：这里直接生成的b包含后续节点，但为了模拟相交，我们会把b的尾部截断并接上a的相交部分
headA = create_linked_list(a)
headB = create_linked_list(b[:3]) # 只生成 [5,6,1]# 模拟相交：相交点是 8
# a中8的位置是索引2 (4->1->8)
intersect_node = headA.next.next # 将b的尾部接上相交节点
curB = headB
while curB.next:curB = curB.next
curB.next = intersect_nodeprint(f"Intersect val: {Solution().getIntersectionNode(headA, headB).val}")
反转链表
每次存三个节点。
from typing import Optional
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:cur=headif(cur==None):return Noneqaq=cur.nexthead.next=Nonewhile(qaq!=None):tmp=qaq.nextqaq.next=curcur=qaqqaq=tmpreturn cur
def init(arr):head=ListNode(arr[0])cur=headfor i in range(1,len(arr)):cur.next=ListNode(arr[i])cur=cur.nextreturn head
arr=[1,2,3,4,5]
print(Solution().reverseList(init(arr)).val)
链表的中间结点
两倍速度指针/先扫一遍记录长度
from typing import Optional
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution:def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:cur=headn=1while(cur.next!=None):n+=1cur=cur.nextn=n//2cur=headwhile(n):cur=cur.nextn-=1return cur
回文链表
先找中点然后反转后半部分。然后双指针同时跑一遍。
from typing import Optional
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution:def reverseList(head):cur=headif(cur==None):return Noneqaq=cur.nexthead.next=Nonewhile(qaq!=None):tmp=qaq.nextqaq.next=curcur=qaqqaq=tmpreturn curdef isPalindrome(self, head: Optional[ListNode]) -> bool:fast=headslow=headwhile(fast.next!=None and fast.next.next!=None):slow=slow.nextfast=fast.next.nexthead2=Solution.reverseList(slow)head1=headif(head1.val!=head2.val):return Falsewhile(head1.next!=None and head2.next!=None):head1=head1.nexthead2=head2.nextif(head1.val!=head2.val):return Falsereturn True
def init(arr):head=ListNode(arr[0])cur=headfor i in range(1,len(arr)):cur.next=ListNode(arr[i])cur=cur.nextreturn head
arr=[1,2,3,2,1]
print(Solution().isPalindrome(init(arr)))
环形链表
哈希表。
from typing import Optional
class ListNode:def __init__(self, x):self.val = xself.next = None
class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:if(head==None):return Falsea=set()cur=heada.add(cur)while(cur.next!=None):cur=cur.nextif(cur in a):return Truea.add(cur)return False
环形链表 II
快慢指针。
from typing import Optional
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:slow=headfast=headif(fast==None):return Noneif(fast.next==None):return Nonewhile(True):slow=slow.nextfast=fast.next.nextif(fast==None or fast.next==None):return Noneif(fast==slow):breakcur=headwhile(slow!=cur):slow=slow.nextcur=cur.nextreturn cur
合并两个有序链表
from typing import Optional
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:cur1=list1cur2=list2if(cur1==None and cur2==None):return Nonehead=ListNode()cur3=headwhile(cur1!=None and cur2!=None):if(cur1.val>cur2.val):cur3.next=cur2cur2=cur2.nextcur3=cur3.nextelse:cur3.next=cur1cur1=cur1.nextcur3=cur3.nextif(cur1!=None):cur3.next=cur1if(cur2!=None):cur3.next=cur2return head.next
删除链表的倒数第 N 个结点
设一个快n-1个结点的指针
from typing import Optional
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:slow=headfast=headfor i in range(n-1):fast=fast.next# if(fast==None):# return Noneif(fast.next==None):tmp=slow.nextslow.next=Nonereturn tmpwhile(fast.next.next!=None):slow=slow.nextfast=fast.nextqaq=slow.next.nextslow.next=qaqreturn head