题目链接

160. 相交链表

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

解题思路

1. 哈希表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

2. 消除长度差

如果两个链表的长度不一样，那么只需要让长度更长的链表先移动「长链表长度 - 短链表长度」步，然后两个链表一起遍历，当遍历到第一个相同节点时即为两个相交链表的起始节点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int len1 = getLength(headA);
    int len2 = getLength(headB);
    while (len1 != len2) {
        if (len1 > len2) {
            headA = headA.next;
            len1--;
        } else {
            headB = headB.next;
            len2--;
        }
    }
    while (headA != headB) {
        if (headA == null || headB == null) {
            return null;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}
public int getLength(ListNode head) {
    int cnt = 0;
    while (head != null) {
        cnt++;
        head = head.next;
    }
    return cnt;
}

• 时间复杂度：，N 取决于长链表的节点个数。
• 空间复杂度：

  3. 更巧妙的消除长度差（数学）

  public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        while (cur1 != cur2) {
            cur1 = cur1 != null ? cur1.next : headB;
            cur2 = cur2 != null ? cur2.next : headA;
        }
        return cur1;
    }
  }