Given two sorted linked lists, where the result should be union without duplicates.
- Creating of new nodes is not allowed.
- The resulting list will be composed of the elements of the original lists.
Inputs are two lists separated by empty line:
L1 -> 2 3 3 4 4 4 5
L2 -> 3 4 5 5 6 7
Result -> 2 3 4 5 6 7
I have my solution below, but creating new node in Union function.
Is there any simple way how to change Union function with the logic of not creating any new node and remove duplicates?
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
CodePudding user response：
I would suggest dealing with the first node separately, so you know what the head will be of the merged list. The rest of your code can remain the same:
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
CodePudding user response：
Without modifying your solution I decided to implement my own, it doesn't create any new Node. It does a regular merge-sort algorithm.
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()
Input:
2 3 3 4 4 4 5
3 4 5 5 6 7
Output:
2 3 4 5 6 7