链表oj(8)----＞相交链表

红太狼 2023-10-02 12:41 18阅读 0赞

题目内容：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

解题代码：

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode cur1 = headA;
            ListNode cur2 = headB;
            int a = 0;
            int b = 0;
            if(cur1 ==null || cur2 == null){
                return null;
            }
            while(cur1 != null){
                a++;
                cur1 = cur1.next;
            }
            while(cur2 != null){
                b++;
                cur2 = cur2.next;
            }
    
            cur1 = headA;
            cur2 = headB;
    
            int k = a - b;
            while( k != 0){
                if(k >= 0){
                    cur1 = cur1.next;
                    k--;
                }else{
                    cur2 = cur2.next;
                    k++;
                }
            }
    
            while(cur1 != null && cur2 != null){
                if(cur1 == cur2){
                    break;
                }else{
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                }
            }
            return cur1;
        }
    }

解题思路：

>  *  先判断两个是否为空，若有一个为空则直接返回空
>  *  遍历两个链表，求出长度，进行比较，让长的一个走多出来的部分
>  *  一起遍历，如果相交结点返回的cur1必然时有结点的，若没有，则是走到空的位置退出循环，返回的也是空。符合题意返回的要求

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8864b3ccf78448eeb79f9530bfc1e3bf.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16