Intersection of Two Linked List

题目描述

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

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

begin to intersect at node c1.

解题方法

reverse list

如果可以有extra space, 可以将两个List都reverse一下，然后找最后的相同点。

no extra space

两个list在Intersection之后的长度是一样的，而在Intersection之前的长度是不一样的，那么找出 长度的差diff，并且将长的那个list的pointer先往前移diff的距离，然后在同时往前， 就可以找到intersection的点。

Solution

# 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 not headA or not headB:
            return None

        lA = self.getLength(headA)
        lB = self.getLength(headB)

        diff = abs(lA - lB)
        if lA < lB:
            p = 0
            while p < diff:
                headB = headB.next
                p += 1
        else:
            p = 0
            while p < diff:
                headA = headA.next
                p += 1

        while headA != headB:
            headA = headA.next
            headB = headB.next

        return headA

    def getLength(self, head):
        if not head:
            return 0

        l = 0
        while head:
            l += 1
            head = head.next

        return l

Reference