算法-链表-链表相交

╰半橙微兮° 2023-07-24 08:33 49阅读 0赞

# 1 简单链表反转 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

## 1.2 题目描述 ##

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 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 个节点。

示例 2：

输入：intersectVal = 2, listA = \[0,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1  
输出：Reference of the node with value = 2  
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 \[0,9,1,2,4\]，链表 B 为 \[3,2,4\]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = \[2,6,4\], listB = \[1,5\], skipA = 3, skipB = 2  
输出：null  
输入解释：从各自的表头开始算起，链表 A 为 \[2,6,4\]，链表 B 为 \[1,5\]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。  
解释：这两个链表不相交，因此返回 null。

注意：

*  如果两个链表没有交点，返回 null 。
 *  在返回结果后，两个链表仍须保持原有的结构。
 *  可假定整个链表结构中没有循环。
 *  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

## 1.3 题解 ##

### 1.3.1 分别遍历并记录对象 ###

#### 1.3.1.1 解题思路 ####

1.  先遍历一个链表，每个节点记录到一个HashSet
2.  再遍历另一个链表，每次都去和HashSet中的记录匹配，首次匹配成功的就是相交节点

#### 1.3.1.2 代码 ####

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
        Set<ListNode> listNodeSet = new HashSet();
        while(headA!=null){ 
            listNodeSet.add(headA);
            headA = headA.next;
        }
    
        while(headB!=null){ 
            if(listNodeSet.contains(headB)){ 
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

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

O(N)

#### 1.3.1.4 空间复杂度 ####

O(N)

*  不满足题目的要求

### 1.3.2 两次遍历 ###

#### 1.3.2.1 解题思路 ####

1.  先分别计算两个链表长度
2.  然后计算两个链表长度差异，让较长的那个先遍历差值个节点
3.  两个链表一起遍历，找到相同对象就是相交节点

#### 1.3.2.2 代码 ####

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
       if(null == headA || null == headB){ 
            return null;
        }
        if(headA == headB){ 
            return headA;
        }
        // 记录原始头节点
        ListNode newHeadA = headA;
        ListNode newHeadB = headB;
    
        // 1. 先分别计算两个链表长度
        int lengthA = 0;
        while(newHeadA != null){ 
            lengthA++;
            newHeadA = newHeadA.next;
        }
        int lengthB = 0;
        while(newHeadB != null){ 
            lengthB++;
            newHeadB = newHeadB.next;
        }
    
        // 2. 这里千万记住重置两个头结点
        newHeadA = headA;
        newHeadB = headB;
    
        // 3. 然后计算两个链表长度差异，让较长的那个先遍历差值个节点
        int differ = lengthA - lengthB;
        int minlength = 0;
        if(differ > 0){ 
            for(int i = 0; i < differ; i++){ 
                newHeadA = newHeadA.next;
            }
            minlength = lengthB;
        }else{ 
            differ = 0 - differ;
            for(int i = 0; i < differ; i++){ 
                newHeadB = newHeadB.next;
            }
            minlength = lengthA;
        }
    
        // 4.两个链表一起遍历，找到相同对象就是相交节点
        while(newHeadA != null){ 
            if(newHeadA == newHeadB){ 
                return newHeadA;
            }else{ 
                newHeadA = newHeadA.next;
                newHeadB = newHeadB.next;
            }
        }
        return null;
    }

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

O(N)

其实是要遍历两次

#### 1.3.2.4 空间复杂度 ####

O(1)

### 1.3.3 走相同的路 ###

#### 1.3.3.1 解题思路 ####

![前][20200410112345612.png]  
如上图

1.  各自从自己链表头结点出发，到达终点后又从另一个链表头结点出发遍历
2.  如果第二次发生相遇，说明首次相遇节点即是相交节点
3.  否则说明无相交

显然只要存在焦点，则 `AC +CD+BC` = `BC+CD+AC`，即刚好在相交节点C相遇，否则无相交

#### 1.3.3.2 代码 ####

public static ListNode getIntersectionNode3(ListNode headA, ListNode headB) { 
        if(null == headA || null == headB){ 
            return null;
        }
        if(headA == headB){ 
            return headA;
        }
        // 记录原始头节点
        ListNode newHeadA = headA;
        ListNode newHeadB = headB;
    
        while(newHeadA != newHeadB){ 
        	// 注意这里必须这样写，不能先移动再判空交换头结点，
        	// 否则可能造成两个相同长度的无相交链表永远无法退出循环
            if(newHeadA == null){ 
                newHeadA = headB;
            }else{ 
                newHeadA = newHeadA.next;
            }
            if(newHeadB == null){ 
                newHeadB = headA;
            }else{ 
                newHeadB = newHeadB.next;
            }
        }
        // 此时newHeadA要么是交点，要么是不相交时的null
        return newHeadA;
    }

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

O(N)

#### 1.3.3.4 空间复杂度 ####

O(1)

[20200410112345612.png]: /images/20230528/500f8413af504895b7b2dbb7930b83c6.png