瑞文考研算法每日一题—2023.05.22相交链表

Problem: 160. 相交链表
此题与408-2012统考真题类似，读者阅读后可以去尝试完成。

方法一：哈希集合

思路

  遍历链表headA，将其元素加入哈希集合。然后遍历headB，判断其是否在哈希集合中。

Code

/*** 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) {set<ListNode*> set;while(headA){set.insert(headA);headA = headA->next;}while(headB){if(set.count(headB))break;headB = headB->next;}return headB;}
};

复杂度

• 时间复杂度:
  $O(m+n)$，其中m为headA的长度，n为headB的长度，需要遍历两个链表各一次。

• 空间复杂度:
  $O(m)$，其中m为headA的长度。

方法二：双指针

思路

  设headA的长度为m，headB的长度为n，公共部分长度为c，headA剩余部分为a，headB剩余部分为b，可得等式。

• $a+c=m$
• $b+c=n$

  将headA的尾部接上headB的头部，headB的尾部接上headA的头部，此时分别遍历两个链表，当重合时两个指针分别走了：

• headA：$m+b=a+c+b$
• headB：$n+a=b+c+a$

  如果两个链表没有交集，则一共走了$m+n$步，此时指向空。

Code

/*** 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* p = headA, *q = headB;while(p != q){p = p ? p->next : headB;q = q ? q->next : headA;}return p;}
};

复杂度

• 时间复杂度:
  $O(m+n)$，其中m为headA的长度，n为headB的长度，需要遍历两个链表各一次。

• 空间复杂度:
  $O(1)$