文章目录

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