160. Intersection of Two Linked Lists

题目描述和难度

题目描述：

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

例如，下面的两个链表：

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

在节点 c1 开始相交。

注意：

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

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

题目难度：简单。
英文网址：160. Intersection of Two Linked Lists 。
中文网址：160. 相交链表。

思路分析

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

参考解答

参考解答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 。