LeetCode hoot100-22

160. 相交链表

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

这道题几分钟就写出来了。应该是几年前做过，这种思想还能一直记得。所以算法题是不会白做的。

我的做法
两个链表如果一个长一个短的话，就让长的那个先往后走【长链表长度和短链表长度的差】。这样两个链表再同步往后走，如果右相交的节点的话，就会同时到达那个节点。注意不要改变链表的头结点不能变，所以要重新定义一个指向头结点的节点来做链表的遍历。

/**
 * 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) {
        int lenA = length(headA);
        int lenB = length(headB);
        int cha = Math.abs(lenA - lenB);
        ListNode aa = headA;
        ListNode bb = headB;
        if (lenA > lenB) {
            while (cha > 0) {
                aa = aa.next;
                cha--;
            }
        } else {
            while (cha > 0) {
                bb = bb.next;
                cha--;
            }
        }
        while (aa != bb && aa != null) {
            aa = aa.next;
            bb = bb.next;
        }
        return aa;

    }

    public int length(ListNode listNode){
        int size = 0;
        while (listNode!=null){
            listNode = listNode.next;
            size ++ ;
        }
        return size;
    }
}

官方解法2
优雅啊。主要思想是长短两个链表都先遍历自己，完了之后去遍历对方链表。如果能有相交节点就能同时到达。A链表长m=a+c(c是A，B链表重合部分)，B链表长n=b+c(c是A，B链表重合部分)。A把自己遍历完了就是a+c,然后去遍历B链表的b那一段。整体就是走了a+c+b。同理，B把自己遍历完了就是b+c，然后去遍历A链表a那段。整体就是走了b+c+a。这个时候两个链表走的长度是相同的，如果重合就会直接相遇。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。