题目

链表定义：

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

题解

1. 双指针法交替遍历

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$ 从两个链表的表头开始遍历，遇到null跳到另一个的表头，如果两个表头重合则重合点为交点，否则两个指针再次指向null时说明两个链表不相交
class Solution {//两种方法。1、先从各自开头开始遍历，遍历到末尾则跳到另一个链表的开头
                //原理是a+c+b = b+c+a
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto *a = headA, *b = headB;//设定两个指向链表头的指针
        while(a != b){//当指针未重合时
            a = a? a->next:headB;//若指针未遍历完，则继续遍历，若遍历完（即到null)处，指向另一条链
            b = b? b->next:headA;//同上
        }
        //若两链表等长且有节点，则在第一次遍历二者就重合了
        //若两链表没有节点，则最后会在遍历结束都指向NULL时返回NULL
        return a;//返回重合处的节点
    }
};

2. 双指针法，unordered_set存值法

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$ 双指针遍历自己的链表，两个指针用一个unordered_set存值，遇到重合的就返回交点
class Solution {//两种方法。2、unordered_set存值
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> m;//设定unordered_set
        auto a = headA, b = headB;//设定指向链表头的指针
        while(a || b){//当两个链表有一个未遍历完
            if(a){//如果a未遍历完
                if(m.count(a)) return a;//查看m中有没有a，如果有，则该点就是相交点
                else m.insert(a);//如果没有，把a插入m
                a = a->next;//a指向下一位
            }
            if(b){//同上
                if(m.count(b)) return b;
                else m.insert(b);
                b = b->next;
            }
        }
        return NULL;//遍历结束均为有相交点，则返回NULL
    }
};