給定兩個排序的鏈表，結果應該是聯合而沒有重復。
- 不允許創建新節點。
- 結果串列將由原始串列的元素組成。
輸入是由空行分隔的兩個串列：
L1 -> 2 3 3 4 4 4 5
L2 -> 3 4 5 5 6 7
結果 -> 2 3 4 5 6 7
我在下面有我的解決方案，但在Union函式中創建新節點。
有沒有什么簡單的方法可以通過不創建任何新節點并洗掉重復項的邏輯來更改Union函式？
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 dedup(head):
current = head
while current:
runner = current
# Check, until runner.next is not None.
while runner.next:
if current.data == runner.next.data:
runner.next = runner.next.next
else:
runner = runner.next
current = current.next
def Union(a, b):
# A dummy node to store the result
dummyNode = Node(0)
headA = a
headB = b
# Tail stores the last node
tail = dummyNode
while True:
# If any of the list gets completely empty
# directly join all the elements of the other list
if headA is None:
tail.next = headB
break
if headB is None:
tail.next = headA
break
# Compare the x of the lists and whichever is smaller is
# appended to the last of the merged list and the head is changed
if headA.data <= headB.data:
tail.next = headA
headA = headA.next
else:
tail.next = headB
headB = headB.next
# Advance the tail
tail = tail.next
# Delete dups and returns the head of the merged list
dedup(dummyNode.next)
return dummyNode.next
uj5u.com熱心網友回復：
我建議單獨處理第一個節點，這樣你就知道合并串列的頭部是什么。其余代碼可以保持不變：
def Union(a, b):
if a is None or b is None: # Deal with this trivial case
a = a or b
dedup(a)
return a
headA = a
headB = b
# Tail stores the last node: process first node
if headA.data <= headB.data:
tail = headA
headA = headA.next
else:
tail = headB
headB = headB.next
head = tail # Remember what the head is of the merged list
while True:
if headA is None:
tail.next = headB
break
if headB is None:
tail.next = headA
break
if headA.data <= headB.data:
tail.next = headA
headA = headA.next
else:
tail.next = headB
headB = headB.next
# Advance the tail
tail = tail.next
# Delete dups and returns the head of the merged list
dedup(head)
return head
uj5u.com熱心網友回復：
第1部分
在不修改您的解決方案的情況下，我決定實作自己的解決方案，它不會創建任何新的 Node.js 解決方案。它執行常規的合并排序演算法。有關更短的解決方案，請參閱我的答案的第 2 部分。
在線試試吧！
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
def create_list(l):
n = None
for e in reversed(l):
n = Node(e, n)
return n
def print_list(l):
if l is None:
return
else:
print(l.data, end = ' ')
print_list(l.next)
def main():
l1, l2 = [list(map(int, input().split())) for i in range(2)]
l1, l2 = create_list(l1), create_list(l2)
r = None
head = None
last = None
while True:
if l1 is None and l2 is None:
break
if l2 is None or l1 is not None and l1.data <= l2.data:
if last is None or last < l1.data:
if r is None:
r = l1
head = r
else:
r.next = l1
r = r.next
last = l1.data
l1 = l1.next
elif l1 is None or l2.data < l1.data:
if last is None or last < l2.data:
if r is None:
r = l2
head = r
else:
r.next = l2
r = r.next
last = l2.data
l2 = l2.next
print_list(head)
main()
輸入：
2 3 3 4 4 4 5
3 4 5 5 6 7
輸出：
2 3 4 5 6 7
第2部分
可以注意到，在我上面的代碼中l1，l2部分代碼是對稱的，因此我通過使用l[i]而不是l1and使代碼更簡單（更短）兩次l2，其中 indexi表示我們是使用l1( l[0]) 還是l2( l[1]) 。這是簡化的代碼：
在線試試吧！
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
def create_list(l):
n = None
for e in reversed(l):
n = Node(e, n)
return n
def print_list(l):
if l is not None:
print(l.data, end = ' ')
print_list(l.next)
def main():
l = [create_list(list(map(int, input().split()))) for i in range(2)]
r, head, last = [None] * 3
while l[0] is not None or l[1] is not None:
i = [1, 0][l[1] is None or l[0] is not None and l[0].data <= l[1].data]
if last is None or last < l[i].data:
if r is None:
r = l[i]
head = r
else:
r.next = l[i]
r = r.next
last = l[i].data
l[i] = l[i].next
print_list(head)
main()
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362060.html