剑指offer 两个链表的第一个公共结点

Posted on |

两个链表的第一个公共结点

题目

Leetcode 160.相交链表
输入两个链表，找出它们的第一个公共结点。

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- 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
        pA,pB=pHead1,pHead2
        while pA!=pB:
            pA=pA.next if pA else headB   # 这里只是确保pA，pB非空，但是不排除pA.next、pB.next是None
            pB=pB.next if pB else headA
        return pA                         # 要么返回相交结点，要么在遍历完A+B后没有返回相交结点，此时None==None，返回的pA是None

方法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
31
32
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def length(self,head):
        count=0
        while head:
            count+=1
            head=head.next
        return count
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        pA,pB=pHead1,pHead2
        lenA,lenB=self.length(pHead1),self.length(pHead2)
        if lenA<lenB:
            n=lenB-lenA
            while n>0:
                n-=1
                pB=pB.next
        else:
            n=lenA-lenB
            while n>0:
                n-=1
                pA=pA.next

        while pA and pB:
            if pA==pB:
                return pA
            pA,pB=pA.next,pB.next
        return None