26、【链表】相交链表(C++版本)
题目描述
题目分析
目标是找到两个链表若相交时的公共结点,那么便需要分析公共结点所具有的特性。
假设链表A和链表B具有公共结点,那么在公共结点处之后,两个链表具有相同长度和数值的结点。而在公共结点之前,两个链表的所具有的结点个数并不一定相等。
因此,若分别从链表A和B的公共结点开始遍历直到遍历到NULL结束,则链表A和链表B的遍历次数一定相等。问题的关键便是如何找到这一部分相等的长度,影响我们无法找到长度的因素是链表A和B公共节点之前的链表,因为公共结点之前的链表长度不一定相等。
因此,我们从链表的长度进行研究。
设链表A的长度为:
a + x = la
其中a为公共结点之前的链表长度,x为从公共结点到最后一个结点的长度,la为链表A的总长度。
设链表B的长度为:
b + x = lb
其中b为公共结点之前的链表长度,x为从公共结点到最后一个结点的长度,lb为链表B的总长度。
而我们可发现a + b + x = la + b = lb + a,根据这一条件,便可以找到等价关系,便找到了边界条件。
所以,la + b = lb + a,即走完A后再走B的前一段距离等于走完B后再走A的前一段距离。
参考文章:
图解相交链表
Intersection of Two Linked Lists (双指针,链表拼接)
代码实现
分别定义一个指针cur_a指向headA和指针cur_b指向headB,当cur_a遍历完headA时,让它指向headB的开头,同理,让cur_b遍历完时,让它指向headA的开头。目的是让两个指针分别走过上述a + b + x
长度的路程,从而消除两个链表之间的长度差。当消除完后,两个链表的下一个结点,便是公共结点。
当走完后,如果为NULL,则说明无公共结点,否则返回的便是公共结点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
if(headA == nullptr && headB == nullptr)
return nullptr;
ListNode* cur_a = headA;
ListNode* cur_b = headB;
while(cur_a != cur_b) {
cur_a = (cur_a ? cur_a->next : headB);
cur_b = (cur_b ? cur_b->next : headA);
}
return cur_a;
}
};
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
p1, p2 = headA, headB
while p1 != p2 :
p1 = p1.next if p1 else headB
p2 = p2.next if p2 else headA
return p1
时间复杂度为O(n),空间复杂度为O(n)
相关文章
- 链表数据结构(C/C++语言实现)
- Mac vscode C++调试 无法输入问题
- C++ explicit关键字
- C/C++基础讲解(十五)之数据结构篇链表操作
- [C++ 面试基础知识总结] 关联容器
- 删除链表的倒数第 N 个结点(C++)
- 移除链表元素(C++)
- 4的幂(C++)
- 两个数组的交集 II(C++)
- VS中c++文件调用c 函数 ,fatal error C1853 预编译头文件来自编译器的早期版本号,或者预编译头为 C++ 而在 C 中使用它(或相反)
- 【华为OD机试 2023最新 】猜字谜(C++ 100%)
- 【华为OD机试 2023】天然蓄水库(C++ Java JavaScript Python)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- 解答私信@被c++折磨头秃的花季美少女 //C++ 写一个带命令行参数的程序,可以实现将参数求和、求平均值以及排序之后输出(参数的数量不确定)。
- c++ vector 初始化_C++--vector()的用法
- C++链表冒泡,归并,插入排序(纯指针)
- 初窥C++11:自己主动类型推导与类型获取
- 观察者模式C++实现
- PAT 1083 C++版
- 【C++】第18篇 详解 C++ 链表
- 【跟学C++】C++链表——List类(Study11)
- C++使用技巧(二十七):回顾函数指针参数、数组参数、结构体函数参数
- 基于C++的Winograd卷积实现(分片+乒乓)
- C/C++开发人员要了解的几大著名C/C++开源库