36两个链表的第一个公共节点

tech2023-01-23  53

文章目录

1.题目2.思路3.代码

1.题目

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

在节点 c1 开始相交。

注意:

如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

2.思路

设置两个指针,一个从headA开始遍历,遍历完headA再遍历headB,另一个从headB开始遍历,遍历完headB再遍历headA,如果有交点,两个指针会同时遍历到交点处。

3.代码

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindFirstCommonNode(self, pHead1, pHead2): # write code here p1 = pHead1 p2 = pHead2 while p1 != p2: if p1 == None: p1 = pHead2 else: p1 = p1.next if p2 == None: p2 = pHead1 else: p2 = p2.next return p2
最新回复(0)