力扣160. 相交链表

传送门：相交链表

解题思路

由于两链表相交必然为y形，所以两个相交链表的后面重合部分一定是长度相等的，长度差别就在两链表前面的不相交部分，因此我们可以提前判断两链表的长度差值，让长链表先走差值的步数，之后双指针同时遍历判断是否重合即可

代码

/** * 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=0;
        int lenB=0;
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        while(nodeA != null){
    
            lenA++;
            nodeA = nodeA.next;
        }
        while(nodeB != null){
    
            lenB++;
            nodeB = nodeB.next;
        }
        ListNode longer = headA;
        ListNode shorter = headB;
        int diff = lenA - lenB;
        if(lenA < lenB){
    
            longer = headB;
            shorter = headA;
            diff = lenB - lenA;
        }
        
        while(diff-- > 0){
    
            longer = longer.next;
        }
        while(longer != null && shorter != null){
    
            if(longer == shorter){
    
                return longer;
            }
            longer = longer.next;
            shorter = shorter.next;
        }
        return null;
    }
}

• 时间复杂度 O(m+n)
• 空间复杂度 O(1)