FXTi's blog
0%

intersection-of-two-linked-lists

Posted on Edited on

Intersection of Two Linked Lists – LeetCode 160

Problem

Description

Write a program to find the node at which the intersection of two singly linked lists begins.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unsigned cntA = 0, cntB = 0;
        ListNode *A = headA, *B = headB;
        while(A){
            ++cntA;
            A = A->next;
        }
        while(B){
            ++cntB;
            B = B->next;
        }
        A = headA; B = headB;
        if(cntA > cntB)
            for(unsigned tmp = cntA - cntB; tmp >= 1 ; --tmp)
                A = A->next;
        if(cntB > cntA)
            for(unsigned tmp = cntB - cntA; tmp >= 1 ; --tmp)
                B = B->next;
        while(A != B){
            A = A->next;
            B = B->next;
        }
        return A;
    }
};

思路

通过长度比对来对齐两条链表，然后在相对的位置查找相同节点。很原始的作法，不是One pass方案但却能保证时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$33$ ms，排名$29.90\%$

Better

思路

这个双指针法妙不可言！通过在触及尾端时开始遍历另一条链表来使双指针间产生一个长度等同于两个链表长度差的偏差量，用这个来等位的查找相等的节点。更妙的是同长不交和不等长不交的情况都被囊括，通过检查尾端元素的手法，短短五行实现完成，服气。时间复杂度$O(n)$，空间复杂度$O(1)$。官方解
耗时$33$ ms，排名$29.90\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *cur1 = headA, *cur2 = headB;
        while(cur1 != cur2){
            cur1 = cur1?cur1->next:headB;
            cur2 = cur2?cur2->next:headA;
        }
        return cur1;
    }
};