【Leetcode 剑指Offer】第 12 天 双指针（简单）
迪丽瓦拉
2024-05-29 13:21:34
0次
文章目录
- 剑指 Offer 25. 合并两个排序的链表
- Python 三元表达式
- 链表常用辅助 cur &&dum
- 剑指 Offer 52. 两个链表的第一个公共节点
剑指 Offer 25. 合并两个排序的链表
题：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:# dum是虚拟头节点，cur指向dum,对他进行操作cur=dum=ListNode(0)while l1 and l2:if l1.val复杂度分析：
时间复杂度 O(M+N) ： M,N 分别为链表的长度，合并操作需遍历两链表。
空间复杂度 O(1) ： 节点引用 dum , cur 使用常数大小的额外空间。
Python 三元表达式
写法 A if x else B ，代表当 x=True时执行 A，否则执行 B
链表常用辅助 cur &&dum
很多题都用到这两个辅助。dum存储一个链表，cur用来指向dum对其进行操作。
返回cur.next—是一个值
返回dum.next—是一个链表【因为结构体定义，存储了后续节点的地址】
剑指 Offer 52. 两个链表的第一个公共节点
这题双指针非常优雅，看题解有图示。
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:a,b=headA,headBwhile a!=b:a=a.next if a else headBb=b.next if b else headAreturn a
复杂度分析：
时间复杂度 O(a+b) ： 最差情况下（即 ∣a−b∣=1, c=0），此时需遍历 a+b个节点。
空间复杂度 O(1)： 节点指针 A , B 使用常数大小的额外空间。
总感觉题目的示例是有误的，示例1中为什么是8,不是1？如果因为skipA = 2, skipB = 3的条件决定，在代码输入中没有这俩条件啊？？