题目
给定两个单链表，查找这两个单链表的第一个交叉节点。
例如：链表list_a为：a1→a2→c1→c2→c3，链表list_b为：b1→b2→b3→c1→c2→c3。那么它们第一个交叉结点为c1。
解析
如果两个链表有交叉结点的话，那么交叉节点之后的其他节点都是相同的，即两个链表的结构是Y字型。
a1→a2↘
c1→c2→c3
b1→b2→b3↗可以先获取两个链表的长度，再设定两个指针分别遍历两个链表：让长度较大的链表指针先走|len(list_a)−len(list_b)|步，然后两个指针同步前进，判断第一个相同的结点。
Python实现
# coding=utf-8
class Node(object):
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def get_list_length(head):
"""获取链表长度"""
length = 0
while head:
length += 1
head = head.next
return length
def get_intersect_node(list_a, list_b):
"""查找链表第一个交叉结点"""
length_a = get_list_length(list_a)
length_b = get_list_length(list_b)
cur1, cur2 = list_a, list_b
if length_a > length_b:
for i in range(length_a - length_b):
cur1 = cur1.next
else:
for i in range(length_b - length_a):
cur2 = cur2.next
flag = False
while cur1 and cur2:
if cur1.value == cur2.value:
print(cur1.value)
flag = True
break
else:
cur1 = cur1.next
cur2 = cur2.next
if not flag:
print('链表没有交叉结点')
if __name__ == '__main__':
list_a = Node('a1', Node('a2', Node('c1', Node('c2', Node('c3'))))) # 构造不带头结点的链表：a1→a2→c1→c2→c3
list_b = Node('b1', Node('b2', Node('b3', Node('c1', Node('c2', Node('c3')))))) # 构造不带头结点的链表：b1→b2→b3→c1→c2→c3
get_intersect_node(list_a, list_b)
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
