LeetCode: 160. Intersection of Two Linked Lists 两链表交叉点

ゝ一世哀愁。 2021-06-24 16:10 294阅读 0赞

**试题：**  
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3  
Output: Reference of the node with value = 8  
Input Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as \[4,1,8,4,5\]. From the head of B, it reads as \[5,0,1,8,4,5\]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = \[0,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1  
Output: Reference of the node with value = 2  
Input Explanation: The intersected node’s value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as \[0,9,1,2,4\]. From the head of B, it reads as \[3,2,4\]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = \[2,6,4\], listB = \[1,5\], skipA = 3, skipB = 2  
Output: null  
Input Explanation: From the head of A, it reads as \[2,6,4\]. From the head of B, it reads as \[1,5\]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.  
Explanation: The two lists do not intersect, so return 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) {
            if(headA==null || headB==null) return null;
            ListNode pa = headA, pb = headB;
            int counta = 0, countb = 0;
            
            while(pa!=null){
                counta++;
                pa = pa.next;
            }
            while(pb!=null){
                countb++;
                pb = pb.next;
            }
            
            pa = headA;
            pb = headB;
            int dif = Math.abs(counta-countb);
            if(counta>countb){
                while(dif!=0){
                    pa = pa.next;
                    dif--;
                }
            }else{
                while(dif!=0){
                    pb = pb.next;
                    dif--;
                }
            }
            while(pa!=pb){
                pa = pa.next;
                pb = pb.next;
            }
            return pa;
            
        }
    }