Day12.1 剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

这题做过 — 利用两个都是递增的特点
如果再开一块空间，两边比较，将数值依次放入新的空间中
时间为： N
空间为：N

最好的当然是利用list1 进行原地排序
好像有两种方式

  • 一种从前向后拼接
  • 一种从后向拼接

前向拼接不好原地处理
后向可以在list 1 上原地拼接

淦 错了 是链表 不是 list

如果是链表的话 那就好办了 直接插入就可以吧。

  • 遍历node1的链表
  • 如果node2.val 如果比node1.val 小 放在node1链表的前面。
  • 否则 不动作 进行下一个比较
  • 保持只向前面插值

使用两个指针 一个指当前 一个指前面

我感觉逻辑上没问题 但是不太行。
考虑到逻辑确实稍稍有些乱 我做一个简化
由于链表不需要开辟n个地址 我就初始化一个假节点，然后从前向后比较 插上链表

  1. class Solution:
  2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         cur = dum = ListNode(0)
  5.         while l1 and l2:
  6.             if l1.val < l2.val:
  7.                 cur.next, l1 = l1, l1.next
  8.             else:
  9.                 cur.next, l2 = l2, l2.next
  11.             cur = cur.next
  12.         cur.next = l1 if l1 else l2
  14.         return dum.next

执行用时：52 ms, 在所有 Python3 提交中击败了46.88%的用户
内存消耗：15.3 MB, 在所有 Python3 提交中击败了77.10%的用户

Day 12.2 剑指 Offer 52. 两个链表的第一个公共节点

image.png
感觉应该用检测环形链表那样，用一个快慢指针。指针重合就说明有环

这题的不同点在

  • 首先不是环 快慢指针无法绕圈
  • 其次不止要确认有 还要确认具体的位置，比如要返回交叉节点的值

直观的想法就是每条链子上放一个指针，遍历 找相遇的点
但是链子不是一样长 emmm 就会赶不上。。

那用一个哈希表来存储前面走过的值可以吗？ — 【可以直接存节点 判断节点在不在 — 但是空间复杂度为n 】

  • 但是能保证同一个值只会出现一次吗 — 存节点可以的

希望有一种时间为 n .空间为1 的解法

题解有模拟循环的一种方法
设计两个指针

  • A指针指向第一条链子A，B指针指向第二条链子B
  • 如果A链短的话，A指针遍历完A链就紧接着遍历B链
  • B指针也是 ，遍历完自己的链子就去遍历A的去

因为如果后面相交 后面的长度一样，前面的长短不一，但是两人都把彼此前面的那一段遍历后(相当于加和)，那一定会相遇
比如：
A链： 3+x
B链： 2+x
A指针遍历 5
B指针也遍历5 就相遇了

有一点问题 ： 题目还告诉了一个信息点
相遇前节点在各链上有几个点
image.png

但是就算是这个信息没有利用起来，找到的节点也应该是1 不能是4 吧
这个结果有点奇怪
image.png
当A 到达1的时候： 走了5+3=8步
当B 到达1的时候： 走了6+2 = 8步

难道上面的比较是必须要同一个节点 — 不能仅仅是同一个val数值
那就算这样 后面的都一样 也应该是8 — 是不是我的代码在识别出相等后又向后多走了一步

好吧 判断条件写错了 一上来直接把A链第一个节点返回了

但是更改后提交在这个案例错误了
image.png
image.png
这个案例代码的逻辑 和我的逻辑一毛一样 

  1. class Solution:
  2.     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
  3.         if headA == None or headB==None:
  4.             return None
  6.         P_a = headA
  7.         P_b = headB
  9.         while (P_a != P_b):
  10.             if P_a == None and P_b == None:
  11.                 return None
  13.             if P_a == None:
  14.                 P_a = headB
  15.             if P_b == None:
  16.                 P_b = headA
  18.             P_a = P_a.next
  19.             P_b = P_b.next
  21.         return P_a


o no 不对 。。我这样在最后一个节点才相交的时候会跑到none上去
所以后面不能直接那么写

  1. class Solution:
  2.     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
  3.         if headA == None or headB==None:
  4.             return None
  6.         P_a = headA
  7.         P_b = headB
  9.         while (P_a != P_b):
  10.             if P_a == None and P_b == None:
  11.                 return None
  13.             if P_a == None:
  14.                 P_a = headB
  15.             else:
  16.                 P_a = P_a.next
  18.             if P_b == None:
  19.                 P_b = headA
  20.             else:
  21.                 P_b = P_b.next
  23.         return P_a

好吧 确实丑的一批
还是人家的格式简洁：

  1. class Solution:
  2.     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
  3.         if headA == None or headB==None:
  4.             return None
  6.         P_a = headA
  7.         P_b = headB
  9.         while (P_a != P_b):
  10.             if P_a == None and P_b == None:
  11.                 return None
  13.             P_a = P_a.next if P_a else headB
  14.             P_b = P_b.next if P_b else headA
  16.         return P_a

简化一下