給定兩個排序的鏈表，結果應該是沒有重復的交集。
- 不允許創建新節點。
- 結果串列將由原始串列的元素組成。
輸入是由空行分隔的兩個串列：
L1 -> 2 3 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
uj5u.com熱心網友回復：
您的解決方案實際上并不能防止重復，如果您在兩個串列中都有重復的數字，那么將 a 和 b 一起推進會導致它們再次匹配并且重復出現在結果中。
相反，您應該將它們都推進到一個新的數字，以防止任何重復。
然后通過將 a 分配給串列并清除其下一個值來重用原始節點，這樣它就不會泄漏到現有串列中。
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 之后遍歷串列將給出與使用該函式之前相同的結果，直到第一個相交的專案被下一次覆寫，然后才會是相交值。
所以認為它已損壞，僅使用回傳值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359135.html
上一篇：Java：理解單向鏈表的實作
下一篇：我如何在流程圖中顯示它？