160. 相交链表

题目

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

如下面的两个链表：

image

在节点 c1 开始相交。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

1.我们通常做这种题的思路是设定两个指针分别指向两个链表头部，一起向前走直到其中一个到达末端，另一个与末端距离则是两链表的 长度差。再通过长链表指针先走的方式消除长度差，最终两链表即可同时走到相交点。

2. 换个方式消除长度差： 拼接两链表。
   设长-短链表为 C，短-长链表为 D （分别代表长链表在前和短链表在前的拼接链表），则当 C 走到长短链表交接处时，D 走在长链表中，且与长链表头距离为 长度差;

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode ha = headA;
        ListNode hb = headB;
        while(ha != hb){
            ha = ha == null ? headB:ha.next;
            hb = hb == null ? headA:hb.next;
        }
        return ha;
    }
}