题目链接

LeetCode

题目描述

输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：

在节点 c1 开始相交。

解题思路

方法一（哈希法）

1. 将第一个链表的每个节点记录在map或者set中

2. 在第二个链表中找到第一个相同的节点返回。 ```cpp /**

   • Definition for singly-linked list.
   • struct ListNode {
   • int val;
   • ListNode *next;
   • ListNode(int x) : val(x), next(NULL) {}

   • }; / // map class Solution { public: ListNode getIntersectionNode(ListNode headA, ListNode headB) { unordered_map mp; ListNode *cur = headA; // 记录第一个链表的节点 while(cur!=nullptr){

        mp[cur] = 1;
        cur = cur->next;

     } cur = headB; // 找到第一个相同的节点 while(cur!=nullptr){

        auto it = mp.find(cur);
        if(it!=mp.end()&&it->second==1){
            return cur;
        }
        cur = cur->next;
     

     } return nullptr;

     } };

/**

• Definition for singly-linked list.
• struct ListNode {
• int val;
• ListNode *next;
• ListNode(int x) : val(x), next(NULL) {}
• }; / // set class Solution { public: ListNode getIntersectionNode(ListNode headA, ListNode headB) {

   set<ListNode*> st;
   while(headA){
       st.insert(headA);
       headA = headA->next;
   }
   while(headB){
       if(st.count(headB)){
           return headB;
       }
       headB = headB->next;
   }
   return NULL;
  

  } }; ```

• 时间复杂度 O(M+N)： 两轮遍历链表，使用 O(M+N) 时间。
• 空间复杂度 O(M) ： 哈希表使用线性大小的额外空间。

  方法二（双指针）

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，当它们相遇时，所指向的结点就是第一个公共结点。

/**
 * 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) {
        if(headA==nullptr||headB==nullptr) return nullptr;
        ListNode *l1=headA,*l2=headB;
        while(l1!=l2){
            l1 = (l1 == nullptr) ? headB : l1->next;
            l2 = (l2 == nullptr) ? headA : l2->next;
        }
        return l1;
    }
};

• 时间复杂度 O(M+N)： 两轮遍历链表，使用 O(N) 时间。
• 空间复杂度 O(1)