Java 判断两个链表是否相交

忘是亡心i 2023-10-09 13:45 36阅读 0赞

#### 文章目录 ####

*  问题描述
 *   *  方法一
     *   *  方法描述
         *  动画演示
         *  代码如下
         *  时间复杂度
     *  方法二
     *   *  方法描述
         *  动画演示
         *  代码如下
         *  时间复杂度

## 问题描述 ##

判断两个链表是否相交，如果两个链表相交，两个链表有相同的结点，如图所示：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

### 方法一 ###

#### 方法描述 ####

最简单粗暴地方法可以设置两个变量分别遍历两个链表，双重for循环，在循环遍历过程中，如果两个变量相等，那么两个链表相交。

#### 动画演示 ####

![1367f142d.gif)][1367f142d.gif]

#### 代码如下 ####

/**
     * Definition for singly-linked list.
     * public class Node {
     *     int val;
     *     Node next;
     *     Node() {}
     *     Node(int val) { this.val = val; }
     *     Node(int val, Node next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public boolean isIntersect(SingleLink link) {
        
             //判断链表是否为null
        	if(link == null) {
        
        		return false;
        	}
        	
        	for(Node p = head; p != null; p = p.next){
        
    			for(Node q = link.head; q != null; q = q.next) {
        
    					if( p == q) {
        
    						return true;
    					}
       			}
            }
            return false;
        }
    }

#### 时间复杂度 ####

假设链表1的长度为m，链表2的长度为n，该方法在双重for循环下的时间复杂度为：**O(m × n)**。

### 方法二 ###

#### 方法描述 ####

判断两个链表是否相交，该两个链表中长度必定有长有短，或者相等，想到这两个的链表长度问题，我们可以得到两个链表的长度的差值diff。同样也是设置两个变量p,q，分别遍历长链表和短链表，与方法一不同的是，p遍历长链表的时候不是从第一个结点开始遍历，而是先让p往后移动diff个结点，然后p和q同时循环往后一个结点，如果p == q,那么两个链表就相交。

#### 动画演示 ####

![在这里插入图片描述][efdecd08aa174ade86a2b482d378d002.gif]

#### 代码如下 ####

/**
     * Definition for singly-linked list.
     * public class Node {
     *     int val;
     *     Node next;
     *     Node() {}
     *     Node(int val) { this.val = val; }
     *     Node(int val, Node next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
    	 //求链表长度
       	 private int size() {
        
            int count = 0;
            for (Node p = head; p != null; p = p.next) {
        
                count++;
            }
            return count;
        }
        //判断两个链表是否相交
        public boolean isIntersect(SingleLink link) {
        
            //安全检测
            if (link == null) {
        
                return false;
            }
         	int size_cur = size();//当前链表长度
            int size_link = link.size();//传进来的链表长度
    
    		//p指向长链表的第一个结点  q指向短链表的第一个结点
            Node p = size_cur > size_link ? this.head : link.head;
            Node q = size_cur > size_link ? link.head : this.head;
            //求两个链表长度差
            int diff = Math.abs(size_cur - size_link);
            //p先往后移动diff个结点
            while (diff-- > 0) {
        
                p = p.next;
            }
    		
    		//p 和 q同时往后移动
            while (p != q) {
        
                p = p.next;
                q = q.next;
            }
            
            //如果p(q)不为null，则两个链表相交，否则不相交
            if(p != null) {
        
            	return true;
            }else {
        
            	return false;
            }
    }

#### 时间复杂度 ####

因为p和q是同时往后移动的，所以时间复杂度为**O(n)**，小于方法一的时间复杂度O(m × n)。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/aba6cf669946431da7df2a1b1f9121c8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[1367f142d.gif]: https://img-blog.csdnimg.cn/c17b828ee7454283bdefe1907dbb84cd.gif
[efdecd08aa174ade86a2b482d378d002.gif]: https://img-blog.csdnimg.cn/efdecd08aa174ade86a2b482d378d002.gif