LeetCode 160. 相交链表

160. 相交链表

LeetCode 160. 相交链表
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

链接 https://leetcode.cn/problems/intersection-of-two-linked-lists/

个人思路

1. 哈希表
   将其中一条链表的结点都储存在列表中，然后循环另一条链表的结点，判断结点是否存在列表中，若循环结束都没有结点存在列表则说明没有相交结点，返回None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        nodeList = []
        while headA:
            nodeList.append(headA)
            headA = headA.next
        while headB:
            if headB in nodeList:
                return headB
            headB = headB.next
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

但非常耗时，至于进阶问题，个人觉得应该用双指针，但没想到具体该怎么做

复杂度分析
时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。
空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。

官方思路

1. 双指针
   （1）使用双指针的方法，可以将空间复杂度降至 O(1)。
   （2）只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。
   （3）当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：
   ① 每步操作需要同时更新指针 pA 和 pB。
   ② 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
   ③ 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针pB 移到链表 headA 的头节点。当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        pA,pB = headA,headB
        while pA != pB:
            pA = pA.next if pA != None else headB
            pB = pB.next if pB != None else headA
        return pA
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

速度快很多

复杂度分析
时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
空间复杂度：O(1)。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/

其他思路

先让两个链表剩余长度相同，然后同步遍历，也是空间 O(1)
好秀，我好像也灵光闪现过这一思路，但觉得要先算出长度就放弃了

class Solution {
public:
    int getLength(ListNode* head) {
        int ans = 0;
        for (;head;head = head->next) ++ans;
        return ans;
    }

    ListNode *getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        int len = 0;
        if (lenA > lenB) {
            len = lenB;
            while (lenA-- > lenB)
                headA = headA->next;
        } else {
            len = lenA;
            while (lenB-- > lenA)
                headB = headB->next;
        }
        while (len--) {
            if (headA == headB)
                return headA;
            headA = headA->next;
            headB = headB->next;
        }
        return nullptr;
    }
};
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