剑指 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 = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # dum是虚拟头节点，cur指向dum,对他进行操作
        cur=dum=ListNode(0)
        while l1 and l2:
            if l1.val<l2.val:
                cur.next=l1
                l1=l1.next
            else:
                cur.next=l2
                l2=l2.next
            cur=cur.next#cur也要往后移动，别忘了，不然一直在一个点在操作了
        cur.next=l1 if l1 else l2
        return dum.next

复杂度分析：
时间复杂度 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,headB
        while a!=b:
            a=a.next if a else headB
            b=b.next if b else headA
        return a   

复杂度分析：
时间复杂度 O(a+b) ： 最差情况下（即 ∣a−b∣=1, c=0），此时需遍历 a+b个节点。
空间复杂度 O(1)： 节点指针 A , B 使用常数大小的额外空间。

总感觉题目的示例是有误的，示例1中为什么是8,不是1？如果因为skipA = 2, skipB = 3的条件决定，在代码输入中没有这俩条件啊？？