leetcode 160. Intersection of Two Linked Lists

短命女 2023-07-13 05:56 5阅读 0赞

**目录**

一、问题描述

二、代码实现

1、常规解法

2、最佳解法

--------------------

[https://leetcode.com/problems/intersection-of-two-linked-lists/][https_leetcode.com_problems_intersection-of-two-linked-lists]

找到两个单链表（链表不存在环）交叉的第一个节点，要求时间O(n)，空间O(1)，同时不能改动链表的原有结构。

## 一、问题描述 ##

测试用例：

![format_png][]

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
    Output: Reference of the node with value = 8
    Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

![format_png 1][]

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
    Output: Reference of the node with value = 2
    Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

![format_png 2][]

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
    Output: null
    Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
    Explanation: The two lists do not intersect, so return null.

如果两个单链表没有交叉，返回null。两个单链表交叉有个隐含特性：由于单链表next指针只有一个，两个单链表的重叠部分肯定是在它们的后面部分，而不可能在前面部分。

## 二、代码实现 ##

### 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 getIntersectionNode1(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            
            //计算A的长度
            ListNode cur = headA;
            int sizeA = 0;
            while (cur != null) {
                sizeA++;
                cur = cur.next;
            }
            
            //计算B的长度
            cur = headB;
            int sizeB = 0;
            while (cur != null) {
                sizeB++;
                cur = cur.next;
            }
            
            //针对一些特殊测试用例
            if (sizeA == 1 && sizeB == 1) {
                return headA == headB ? headA : null;
            }
            
            System.out.println(headA.val+"  "+headB.val);
            if (sizeA > sizeB) {
                ListNode temp = headA;
                headA = headB;
                headB = temp;
            }
            System.out.println(headA.val+"  "+headB.val);
            
            //now headB is longer
            int count = Math.abs(sizeA - sizeB);
            //while (headB != null) {
            //error
            while (headB != null && count>0) {
                count--;
                headB = headB.next;
            }
            
            //now headA's length == headB's length 
            while (headB != null) {
                //if (headB.val == headA.val) {
                //input:8   [4,1,8,4,5]  [5,0,1,8,4,5]  2  3
                //output: Intersected at '1'   expected: Intersected at '8'
                if (headB == headA) {
                    break;
                }    
                headB = headB.next;
                headA = headA.next;
            }
            
            
            //the first node  or  null
            return headB;
        }
    }

更简洁的写法：

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            
            ListNode A = headA, B = headB;
            int i = 0, j = 0;
            while (A.next != null) {
                A = A.next;
                i++;
            }
            while (B.next != null) {
                B = B.next;
                j++;
            }
            
            //A == B
            if (A == B) {
                while (i > j) {
                    headA = headA.next;
                    i--;
                }
                while (j > i) {
                    headB = headB.next;
                    j--;
                }
                
                if (headA == headB) {
                    return headA;
                }
                while (headA.next != null && headB.next != null) {
                    if (headA.next == headB.next) {
                        return headA.next;
                    }
                    
                    headA = headA.next;
                    headB = headB.next;
                }
            }
            
            //A != B
            return null;
        }
        
    }

### 2、最佳解法 ###

假设链表A为a\*c，链表B为b\*c，\*为两者第一个共同节点，c为除第一个共同节点外的共同部分。从头遍历链表a\*cb\*c、b\*ca\*c，由于a\*cb和b\*ca长度相同，我们肯定能遍历到第二个\*，也就是链表A和链表B的第一个共同节点。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        //O(n+m)
        public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            
            ListNode A = headA, B = headB;
            //Time Limit Exceeded
    //         while (A != null && B != null) {
    //             if (A == B) {
    //                 return A;
    //             }
                
    //             A = A.next;
    //             B = B.next;
                
    //             if (A == null) {
    //                 A = headB;
    //             }
    //             if (B == null) {
    //                 B = headA;
    //             }
    //         }
    //        return null;
            while (A != null && B != null && A != B) {            
                A = A.next;
                B = B.next;
                
                //两种退出条件：A == B找到第一个共同节点、null == null遍历完两遍之后还找不到（O(n+m)）
                if (A == B) {   //没有这一段会Time Limit Exceeded
                    return A;
                }
                
                if (A == null) {
                    A = headB;
                }
                if (B == null) {
                    B = headA;
                }
            }
            return A;
            
        }
    
    }

参考：

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49789/My-accepted-simple-and-shortest-C%2B%2B-code-with-comments-explaining-the-algorithm.-Any-comments-or-improvements][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_49789_My-accepted-simple-and-shortest-C_2B_2B-code-with-comments-explaining-the-algorithm.-Any-comments-or-improvements]（最佳解法）

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50020/Stupid-and-short-c%2B%2B-solution-without-any-list-cycles-O(N)-time-O(1)-memory][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50020_Stupid-and-short-c_2B_2B-solution-without-any-list-cycles-O_N_-time-O_1_-memory]

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50011/My-java-solution-using-HashSet][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50011_My-java-solution-using-HashSet]（HashSet）

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50079/Another-solution-runs-in-O(n)-time-using-O(1)-space][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50079_Another-solution-runs-in-O_n_-time-using-O_1_-space]（反转链表）

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50049/A-dirty-cheating-solution-(O(n)-time-O(1)-space)][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50049_A-dirty-cheating-solution-_O_n_-time-O_1_-space]（一种巧妙的解法）

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50078/C%2B%2B-solution-o(n)-and-o(1)-Store-access-flag-on-the-next-field-of-ListNode][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50078_C_2B_2B-solution-o_n_-and-o_1_-Store-access-flag-on-the-next-field-of-ListNode]（连接链表）

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50082/C%2B%2B-solution-in-O(n)-time-and-O(1)-space][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50082_C_2B_2B-solution-in-O_n_-time-and-O_1_-space]

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50074/Sharing-my-Java-O(n)-solution][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50074_Sharing-my-Java-O_n_-solution]

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50089/Simple-Java-solution-time-O(n)-space-O(1).-Just-get-the-difference-in-sizes-and-iterate.][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50089_Simple-Java-solution-time-O_n_-space-O_1_.-Just-get-the-difference-in-sizes-and-iterate.]

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50002/Very-Simple-C%2B%2B-Solution][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50002_Very-Simple-C_2B_2B-Solution]

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49792/Concise-JAVA-solution-O(1)-memory-O(n)-time][https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_49792_Concise-JAVA-solution-O_1_-memory-O_n_-time]

[https_leetcode.com_problems_intersection-of-two-linked-lists]: https://leetcode.com/problems/intersection-of-two-linked-lists/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUuY29tL3VwbG9hZHMvMjAxOC8xMi8xMy8xNjBfZXhhbXBsZV8xLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUuY29tL3VwbG9hZHMvMjAxOC8xMi8xMy8xNjBfZXhhbXBsZV8yLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUuY29tL3VwbG9hZHMvMjAxOC8xMi8xMy8xNjBfZXhhbXBsZV8zLnBuZw?x-oss-process=image/format,png
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_49789_My-accepted-simple-and-shortest-C_2B_2B-code-with-comments-explaining-the-algorithm.-Any-comments-or-improvements]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49789/My-accepted-simple-and-shortest-C%2B%2B-code-with-comments-explaining-the-algorithm.-Any-comments-or-improvements
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50020_Stupid-and-short-c_2B_2B-solution-without-any-list-cycles-O_N_-time-O_1_-memory]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50020/Stupid-and-short-c%2B%2B-solution-without-any-list-cycles-O%28N%29-time-O%281%29-memory
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50011_My-java-solution-using-HashSet]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50011/My-java-solution-using-HashSet
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50079_Another-solution-runs-in-O_n_-time-using-O_1_-space]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50079/Another-solution-runs-in-O%28n%29-time-using-O%281%29-space
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50049_A-dirty-cheating-solution-_O_n_-time-O_1_-space]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50049/A-dirty-cheating-solution-%28O%28n%29-time-O%281%29-space%29
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50078_C_2B_2B-solution-o_n_-and-o_1_-Store-access-flag-on-the-next-field-of-ListNode]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50078/C%2B%2B-solution-o%28n%29-and-o%281%29-Store-access-flag-on-the-next-field-of-ListNode
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50082_C_2B_2B-solution-in-O_n_-time-and-O_1_-space]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50082/C%2B%2B-solution-in-O%28n%29-time-and-O%281%29-space
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50074_Sharing-my-Java-O_n_-solution]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50074/Sharing-my-Java-O%28n%29-solution
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50089_Simple-Java-solution-time-O_n_-space-O_1_.-Just-get-the-difference-in-sizes-and-iterate.]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50089/Simple-Java-solution-time-O%28n%29-space-O%281%29.-Just-get-the-difference-in-sizes-and-iterate.
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_50002_Very-Simple-C_2B_2B-Solution]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/50002/Very-Simple-C%2B%2B-Solution
[https_leetcode.com_problems_intersection-of-two-linked-lists_discuss_49792_Concise-JAVA-solution-O_1_-memory-O_n_-time]: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49792/Concise-JAVA-solution-O%281%29-memory-O%28n%29-time