相交链表

Trace

6.4 每日一题

传送门：<https://leetcode-cn.com/problems/intersection-of-two-linked-lists/>

Problem

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

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

input与output看程序模板就好，看题面容易被误导，这里的交点是指地址相同，而不是值相同。

方法一：哈希表

因为同一条链表的结点一定不相同，所以可以用unordered_set来存结点。

然后遍历另外一条链表，去unordered_set中找是否有相同的节点存在。

unordered_set是采用哈希实现的，各种操作的时间复杂度可以看作$O(1)$。

时间复杂度$O(n1+n2)$，空间复杂度$O(n1）$

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> ust;
        ListNode* tmp=headA;
        while(tmp!=NULL){
            ust.insert(tmp);
            tmp=tmp->next;
        }
        tmp=headB;
        while(tmp!=NULL){
            if(ust.count(tmp)){
                return tmp;
            }
            tmp=tmp->next;
        }
        return NULL;
    }
};

方法二：双指针

如果两条链表其中一条为NULL，则没有交点，返回NULL；

t1指向headA的头结点，t2指向headB的头结点，t1与t2每次都向后移动一位，如果$t1->next==NULL$，则t1从headB的头结点开始遍历；如果$t2->next==NULL$，则t2从headA的头结点开始遍历。

如果t1与t2同时为NULL，则返回NULL，无交点；

如果$t1==t2$，则返回t1，t1为交点。

正确性

无交点：链表A与链表B长度相同，t1与t2同时为NULL；链表A与链表B长度不同，t1与t2在把两条链表都遍历完后同时为NULL。

有交点：链表A与链表B长度相同，遍历到交点时$t1==t2 !=NULL$；链表A与链表B长度不同，t1与t2在遍历完原来的链表后在遍历另一条链表时，会同时到达交点$t1==t2=!NULL$。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL) return NULL;
        ListNode* t1=headA;
        ListNode* t2=headB;
        while(1){
            if(t1==t2) return t1;
            t1=t1->next;
            t2=t2->next;
            if(t1==NULL||t2==NULL){
                if(t1==NULL&&t2==NULL) return NULL;
                else if(t1==NULL) t1=headB;
                else t2=headA;
            }

        }   
        return NULL;
    }
};