链表----160. 相交链表

分手后的思念是犯贱 2022-11-16 01:55 319阅读 0赞

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

如下面的两个链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
在节点 c1 开始相交。  
示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
输入：intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3  
输出：Reference of the node with value = 8  
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,0,1,8,4,5\]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。  
【思路】  
①判断两个链表头结点不为空  
②两个指针pa pb 分别指向两个节点  
③进入循环 （pa != pb）  
④如果pa == null ， pa 指向headB 否则pa 指向pa的下一个节点 （即走完heada 走headb链表）  
如果pb == null， pb指向headA 否则pb指向pb的下一个节点（走完headB 走headA链表）  
⑤返回pa  
【代码】

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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20221022/bed3539208a24d559ed8246edeaf5705.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/a4b4ee29d428400085d9097107253da9.png