[剑指Offer]两个链表的第一个公共结点

题目描述

输入两个链表,找出它们的第一个公共结点。

解题思路

  1. 方法一:得到两个链表的长度,然后让长的链表先走长度差步,再同时走,遇到相同的结点即为第一个公共结点。
  2. 方法二:两个链表同时走,将走过的记录下来,并同时判断当前结点是否在另一个链表的记录中,一方走完时,公共结点肯定在另一个链表剩下的部分。

代码

Python(2.7.3)

方法一

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
# -*- 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
c1, c2 = 0, 0
cur1, cur2 = pHead1, pHead2
while cur1 is not None:
c1 += 1
cur1 = cur1.next
while cur2 is not None:
c2 += 1
cur2 = cur2.next
if c1 > c2:
while c1 - c2 > 0:
pHead1 = pHead1.next
c1 -= 1
else:
while c2 - c1 > 0:
pHead2 = pHead2.next
c2 -= 1
while pHead1 != pHead2:
pHead1 = pHead1.next
pHead2 = pHead2.next
return pHead1

运行时间:25ms
占用内存:5728k

方法二

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
# -*- 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
nodes1 = []
nodes2 = []
node1 = pHead1
node2 = pHead2
while node1 is not None and node2 is not None:
if node1 == node2 or node1 in nodes2:
return node1
if node2 in nodes1:
return node2
nodes1.append(node1)
nodes2.append(node2)
node1 = node1.next
node2 = node2.next
if node1 is None:
while node2 is not None and node2 not in nodes1:
node2 = node2.next
return node2
if node2 is None:
while node1 is not None and node1 not in nodes2:
node1 = node1.next
return node1

运行时间:27ms
占用内存:5728k