160. 相交链表

╰+攻爆jí腚メ 2023-02-09 05:25 143阅读 0赞

# 题目来源 #

[160. 相交链表][160.]  
[面试题 02.07. 链表相交][02.07.]  
[剑指 Offer 52. 两个链表的第一个公共节点][Offer 52.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

如果两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束。  
因为两个链表中有一个共同节点，则这个节点里的指针域指向的下一个节点地址一样，所以下一个节点也会相交，依次类推。所以，若相交，则两个链表呈“Y”字形。如下图：  
![在这里插入图片描述][20200518131623105.png]

## 使用栈 ##

从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点。每遍历一个节点时，就将该节点入栈。两个链表都入栈结束知乎，则通过top判断栈顶的节点是否相等，如果相等则两个链表相交：如果两个链表相交，则从第一个相交节点开始，后面的节点都相交。

如果两链表相交，则循环出栈，知道遇到两个出栈的节点不相同，则这个节点的后一个节点就是第一个相交的节点。

栈问题要：小心栈溢出

![在这里插入图片描述][20200518133552720.png]

## 遍历记录链表长度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

/**
     * 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 tempA = headA;
            int al = 1;
            while (tempA.next != null){
        
                al++;
                tempA = tempA.next;
            }
    
            ListNode tempB = headB;
            int a2 = 1;
            while (tempB.next != null){
        
                a2++;
                tempB = tempB.next;
            }
    
            if (tempA != tempB){
        
                return null;
            }
    
            int diff = Math.abs(al - a2);
            if (al >= a2){
        
                tempA = headA;
                tempB = headB;
            }
            
            if (a2 > al){
        
                tempA = headB;
                tempB = headA;
            }
            
            for (int i = 0; tempA != null && i < diff; i++){
        
                tempA = tempA.next;
            }
            
            while (tempA != null  && tempB != null && tempA != tempB){
        
                tempA = tempA.next;
                tempB = tempB.next;
            }
            
            
            return tempA;
        }
    }

![在这里插入图片描述][20200518150611969.png]

## 使用set ##

还可以使用hash

遍历链表A，将A中节点对应的指针（地址）插入set中；  
遍历链表B，将B中节点对应的指针（地址）在set中查找，发现在set中的第一个节点地址，即为两个链表的交点。

![在这里插入图片描述][20200518153601981.png]

## 双指针 ##

思路是双指针，分别指向两个链表的头节点，循环这个链表，之后再去循环另一个链表。

分为两种情况：

一种是没有交点；  
![在这里插入图片描述][20200518154226108.png]  
循环之后就返回 NULL，因为没有交点。

另一种是有交点；  
![在这里插入图片描述][20200518154237548.png]  
原理：  
![在这里插入图片描述][20200624161547124.png]  
AD + DC + BD = BD + DC + AD

public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            if (headA == null || headB == null){
          // 只要有一个是空链表，就一定不会相交
                return null;
            }
    
            ListNode p1 = headA;
            ListNode p2 = headB;
            
            while (p1 != p2){
        
                p1 = p1 == null ? headB : p1.next;
                p2 = p2 == null ? headA : p2.next;
            }
            
            return p1;
        }
    }

![在这里插入图片描述][2020051815482429.png]

[参考][Link 1]

[160.]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[02.07.]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
[Offer 52.]: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200624165402288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200518131623105.png]: https://img-blog.csdnimg.cn/20200518131623105.png
[20200518133552720.png]: https://img-blog.csdnimg.cn/20200518133552720.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200518133756550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200518150611969.png]: https://img-blog.csdnimg.cn/20200518150611969.png
[20200518153601981.png]: https://img-blog.csdnimg.cn/20200518153601981.png
[20200518154226108.png]: https://img-blog.csdnimg.cn/20200518154226108.png
[20200518154237548.png]: https://img-blog.csdnimg.cn/20200518154237548.png
[20200624161547124.png]: https://img-blog.csdnimg.cn/20200624161547124.png
[2020051815482429.png]: https://img-blog.csdnimg.cn/2020051815482429.png
[Link 1]: https://blog.csdn.net/fengxinlinux/article/details/78885764