Leetcode-160-相交链表

Leecode-160-Intersection of Two Linked Lists

思路：

题目描述：

编写一个程序，找到两个单链表相交的起始节点。

如下图所示：

输入：
listA = [4,1,8,4,5]
listB = [5,0,1,8,4,5]

输出：Reference of the node with value = 8

不相交如下：

输入：
listA = [2,6,4]
listB = [1,5]

输出：null

Solution：

• 思路：如果两个链表相交，那么相交点之后的长度是相同的（让两个链表走过相同的路程）（消除两个链表的长度差）

// 1. 如果pA先到达末尾，则pA = headB 继续从头遍历
// 2. 如果pB先到达末尾，则pB = headA 继续从头遍历

1. 初始化pA和pB

2. 依次遍历

3. pB到达末尾，指向链表A的头部，此时A和B长度差是B的长度3

4. pA到达末尾，移动到B链表的头部

5. 这是pA和pB到达最后null的长度就是一样的了

Java

Solution :

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 特判
    if (headA == null || headB == null) return null;
    // 初始化：指针pA指向A链表，指针pB指向B链表
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
    // 1. 如果pA先到达末尾，则pA = headB 继续从头遍历
    // 2. 如果pB先到达末尾，则pB = headA 继续从头遍历
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    // 相交部分即使pA也是pB
    return pA;
}

换一种解释：

若相交，链表A： a+c, 链表B : b+c. a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。若不相交，a +b = b+a 。因此相遇处是NULL

• 时间复杂度：O(n) 遍历链表即可

• 空间复杂度：O(1) 不需要额外的空间

Python

Solution :

打赏