C/C++教程

【Leetcode】160. 相交链表

本文主要是介绍【Leetcode】160. 相交链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 一. 题目信息
    • 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;
    }
};
这篇关于【Leetcode】160. 相交链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!