面试题 02.07. 链表相交

2023-11-21

面试题 02.07. 链表相交 - 力扣（LeetCode）

思路：

1 暴力法：判断的是next是不是相等

1 hashmap存储其中一个的全部，遍历另一个看是不是在map中（用set就行，不用map）

2 双指针：用2个指针分别遍历2链表（都是遍历完一个继续遍历另一个），最终会相等的，

相等就是找到了

暴力法：

/**
 * 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 l1=new ListNode();
        l1.next=headA;
        ListNode l2=new ListNode();
        l2.next=headB;
 
 
        boolean f=false;
 
        ListNode temp1 =l1;
        ListNode temp2=l2;
        while(temp1.next!=null){
            while(temp2.next!=null){
                if(temp1.next==temp2.next){
                    break;
                }
                temp2=temp2.next;
            }
 
 
            if(temp2!=null && temp1.next==temp2.next){
                f=true;
                break;
            }
            temp2=l2;
            temp1=temp1.next;
        }
 
        if(f){
            return temp1.next;
        }
 
        return null;
 
    }
}

hashmap：这里用的是set集合

/**
 * 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) {
       //时间复杂度可以降低为O（n），借助1个set就行，，但是空间占用多，还可以优化
 
       //此链表相交特殊，没有x型相交的， 所以第一个相交的点之后一定是全部相交的
       //链表的相交也不可能是x型，交点的后一个一定确定的
       //时间复杂度为O（n） ，且O（1）内存
 
        //2个天才思路
        //2思路最坏情况效率一样，其余都是2方法效率高
 
            //1 先后指针
            //先统计2链表长度，长度差就是先指针在长链表先走的距离，
            //然后2指针一起走，直到出现相等就是找到了 / 都走到最后，就是没有
 
            //2 双指针           
            //2指针从2链表开始一起走，出现相等就找到了，出现一个指针走完，让其转到另一个链表开头继续
            // 1  3
            // 1  3
            // 1----------3
            // 2----------3
            // 1-3-2     2-3-1
            //有就一定会出现相等的情况，都转了后还是都为null，说明没有
 
 
    //借助set
        if(headA==null || headB==null){
            return null;
        }
 
        ListNode a=headA;
 
        Set<ListNode> set=new HashSet<ListNode>();
        while(a!=null){
            set.add(a);
            a=a.next;
        }
 
 
        ListNode b=headB;
        while(b!=null){
            if(set.contains(b)){
                return b;
            }
            b=b.next;
        }
 
        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) {
       //时间复杂度可以降低为O（n），借助1个set就行，，但是空间占用多，还可以优化
 
       //此链表相交特殊，没有x型相交的， 所以第一个相交的点之后一定是全部相交的
       //链表的相交也不可能是x型，交点的后一个一定确定的
       //时间复杂度为O（n） ，且O（1）内存
 
        //2个天才思路
        //2思路最坏情况效率一样，其余都是2方法效率高
 
            //1 先后指针
            //先统计2链表长度，长度差就是先指针在长链表先走的距离，
            //然后2指针一起走，直到出现相等就是找到了 / 都走到最后，就是没有
 
            //2 双指针           
            //2指针从2链表开始一起走，出现相等就找到了，出现一个指针走完，让其转到另一个链表开头继续
            // 1  3
            // 1  3
            // 1----------3
            // 2----------3
            // 1-3-2     2-3-1
            //有就一定会出现相等的情况，都转了后还是都为null，说明没有
 
    //优雅双指针
        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;
 
 
 
    }
}