Leetcode-Intersection of Two Linked Lists

发表于 | 分类于 |

Intersection of Two Linked Lists

寻找两个无环链表的交点。
Description

解题思路：

  1. 如果两个链长度相同的话，那么对应的一个个比下去就能找到；
  2. 如果两个链长度不相同，分别计算出两个链表的长度，计算出长度差值，然后让长度更长的那个链表从头节点先遍历长度差的步数，这样以后两个链表按尾部对齐。接着长链表和短链表同步往下走，遇到的第一个相同的节点就是最早的公共节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 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
        """
        lenA = lenB = 0
        curA, curB = headA, headB 
        while curA is not None:
            lenA += 1
            curA = curA.next
        while curB is not None:
            lenB += 1
            curB = curB.next
        if lenA>lenB:
            for i in range(lenA-lenB):
                headA = headA.next
        else:
            for i in range(lenB-lenA):
                headB = headB.next
        while headA != headB:
            headA = headA.next
            headB = headB.next
        return headA