算法练习(11) - 寻找相交链表的相交节点

题目 : 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

结果

答案

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        int al = 0;
        while(pa != null){
            al++;
            pa = pa.next;
        }

        ListNode pb = headB;

        int bl = 0;
        while(pb != null){
            bl++;
            pb = pb.next;
        }
        int step = 0;
        if(al > bl){
            step = al -bl;
            int s = 0;
            while(headA != null && s < step){
                headA = headA.next;
                s++;
            }
            while (headA != headB){
                headA = headA.next;
                headB = headB.next;
            }
            return headA;

        }else{
            step = bl -al;
            int s = 0;
            while(headB != null && s < step){
                headB = headB.next;
                s++;
            }
            while (headA != headB){
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }
    }
}

思路

将长度比较长的链表指针提前赶到短链表的头结点位置,然后2个指针以同样步伐一步一步往下走,直到找到相交节点或返回空值