## LeetCode 88

### Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

### Solution

$i\leftarrow m, j\leftarrow n, k\leftarrow m+n$，这样能保证$i < k$。

Python Code:

## LeetCode 160

### Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Example 2:

Example 3:

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in $O(n)$ time and use only $O(1)$ memory.

### Solution 2: $O(N\log M)$

Solution 1的改进，显然$judge$函数是单调的，可以二分答案，二分查找C到$Head_A$的距离。

### Solution 3: $O(1)$

$$a + c + b = b + c + a$$

$$||A \rightarrow C || + ||C\rightarrow D|| + ||B\rightarrow C|| = ||B \rightarrow C || + ||C\rightarrow D|| + ||A\rightarrow C||$$

• 同时分别从A, B出发，前进速度一样，每次前进一格。
• 当$p$到达D，$p$下一步转移到B。
• 当$q$到达D，$q$下一步转移到A。

C++ Code：

------ 本文结束------
0%