给定两个排序的链表，其中的结果应该是交集，而不是对偶。
- 不允许创建新节点
- 生成的列表将由原始列表的元素组成
输入是由空行分隔的两个列表：
L1->2 3 4 4 4 5
L2->3 4 5 6 7
结果->3 4 5
下面是我的解决方案，但在IntersectionDestruct函数中创建新节点。
有什么简单的方法可以用不创建任何新节点的逻辑来更改IntersectionDestruct函数吗？
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
def PrintLinkedList( p ):
print( "Result:", end=" " )
while p!=None:
print( p.data, end=" " )
p = p.next
print(".")
def ReadLinkedList():
first = None
last = None
r = input()
while r!="":
row = r.split()
if len(row)==0:
break
for s in row:
p = Node(int(s),None)
if first==None:
first = p
else:
last.next = p
last = p
r = input()
return first
def LLIntersection(a, b):
head = tail = None
while a and b:
if a.data == b.data:
if head is None:
head = Node(a.data, head)
tail = head
else:
tail.next = Node(a.data, tail.next)
tail = tail.next
a = a.next
b = b.next
# advance the smaller list
elif a.data < b.data:
a = a.next
else:
b = b.next
return head
您的解决方案实际上并不能防止重复，如果两个列表中都有重复的数字，那么将a和b放在一起会导致它们再次匹配，结果中会出现重复。
相反，您应该将它们都提前到新的编号，这样可以防止任何重复。
然后，只需通过为列表指定并清除其下一个值来重用原始节点，这样它就不会泄漏到现有列表中。
def IntersectionUnique(a, b):
head = tail = None
while a and b:
if a.data == b.data:
if head is None:
head = tail = a
else:
tail.next = a
tail = a
# Skip past all duplicates (careful for end of list!)
while a.next and a.data == a.next.data:
a = a.next
while b.next and b.data == b.next.data:
b = b.next
# Advance to new values
a = a.next
b = b.next
# Clear tail
tail.next = None
# advance the smaller list
elif a.data < b.data:
a = a.next
else:
b = b.next
return head
由于这会覆盖a中节点上的下一个值，因此在这之后从a遍历列表将给出与使用该函数之前相同的结果，直到第一个相交的项被覆盖，然后才是相交的值。
因此，如果它已损坏，请仅使用返回值。