文章目录

• 一. 题目信息
• • 1. 描述
• 二. 解法
• • 1. 双指针
  • • ①. 复杂度分析
    • ②. c++解法

一. 题目信息

1. 描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

二. 解法

1. 双指针

核心是走的路程相同

①. 复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

②. c++解法

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