以下是一个示例代码,用于找到两个链表的共同节点,并按照它们出现的顺序进行排序:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
# 计算链表A的长度
lenA = 0
currA = headA
while currA:
lenA += 1
currA = currA.next
# 计算链表B的长度
lenB = 0
currB = headB
while currB:
lenB += 1
currB = currB.next
# 将两个链表的指针移动到相同的起点
currA, currB = headA, headB
if lenA > lenB:
for _ in range(lenA - lenB):
currA = currA.next
else:
for _ in range(lenB - lenA):
currB = currB.next
# 遍历链表,找到共同节点
while currA and currB:
if currA == currB:
return currA
currA = currA.next
currB = currB.next
# 如果没有共同节点,则返回None
return None
使用示例:
# 创建链表A
a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
a4 = ListNode(6)
a5 = ListNode(7)
a1.next = a2
a2.next = a3
a3.next = a4
a4.next = a5
# 创建链表B
b1 = ListNode(4)
b2 = ListNode(5)
b1.next = b2
b2.next = a4 # 共同节点
# 找到共同节点并按出现顺序排序
intersection = getIntersectionNode(a1, b1)
if intersection:
result = []
while intersection:
result.append(intersection.val)
intersection = intersection.next
print(result) # 输出 [6, 7]
else:
print("No intersection")
以上代码中,首先计算两个链表的长度,然后将指针移动到相同的起点,最后遍历链表,找到共同节点。输出结果为按出现顺序排序的共同节点。如果没有共同节点,则输出"No intersection"。