160. Intersection of Two Linked Lists

题目描述和难度

  • 题目描述:

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

 

例如,下面的两个链表

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始相交。

 

注意:

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

 

致谢:
特别感谢 @stellari 添加此问题并创建所有测试用例。

思路分析

求解关键:两个链表不一样长,就想办法让它们一样长。

参考解答

参考解答1

Python 写法:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# 思路:两个链表不一样长,就想办法让它们一样长。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return None
        node1 = headA
        node2 = headB
        while node1 != node2:
            if node1:
                node1 = node1.next
            else:
                node1 = headB
            if node2:
                node2 = node2.next
            else:
                node2 = headA
        return node1

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0160-intersection-of-two-linked-lists ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com