长大后想做什么？做回小孩！

0%

LeetCode——相交链表

发表于 分类于 Valine：
本文字数： 408

NO.160 相交链表 简单

YAEFAS.png

YAEC0f.png

YAEP78.png

思路一：两次遍历 如果两个链表长度相同，那么问题就简单了，直接两个指针分别遍历两个链表，指针相等则找到交点。所以我们要做的就是找到两个指针遍历的起点，消除长度差。

示例一：

intersectVal = 8

headA [ 4,1,8,4,5]

headB [8,0,1,8,4,5]

需要让两个指针 pa从headA的头节点4开始，pb从headB的节点0开始，去同步遍历。

这个4和0如何找到呢？

  1. 先让pa和pb同时步进遍历两个链表，当pa遍历完headA就去遍历headB，pb遍历完headB就去遍历headA
  2. pa一定先遍历完指向了headb的头节点8，当pb遍历完headB指向headA的时候，pa到达节点0，此时就实现了消除了长度差，继续同步步进遍历，pa和pb会同时到达相交节点8
1
2
3
4
5
6
7
8
9
10
11
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pa = headA, pb = headB;
    //找到交点 或者 pa和pb第二次遍历都完成 时跳出循环
    while (pa != pb) {
        //pa 或 pb 遍历完成后指向另一条链表
        pa = pa == null ? headB : pa.next;
        pb = pb == null ? headA : pb.next;
    }
    return pa;
}

时间复杂度：O(n) 最坏情况两次完整的遍历

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github