CODEWITHSUNDEEP
pythonlinked-listiteratormergesort
Shweta
Shweta

Reputation: 1161

python with two iterators increment one at a time

I am a newbie in python.

I tried implementing something like merge sort in python. I used singly linked list from https://pythonhosted.org/llist/#sllist-objects. To merge two sorted list, i need to traverse both lists with iterator. The pseudo code looks something like:

n3 = sllist()
for n1 in list1 and n2 in list2:
    if (n1 > n2):
        n3.append(n1)
        n1++               # c way of doing thing
    else:
        n3.append(n2)
        n2++               # c way of doing thing

But I don't know how to make this working in python. Any pointer or hint will help.

Edit: After all the discussions and suggestions, I came up with code something like this. Can anyone tell me, how to get rid of last two while loops. I was planning to use "extend" but unable to use it.

final_list = sllist()
node1 = list1.first
node2 = list2.first

while node1 and node2:
    if node1.value < node2.value:
        final_list.append(node1)
        node1 = node1.next              
    else:
        final_list.append(node2)
        node2 = node2.next
while node1:
    final_list.append(node1)
    node1 = node1.next
while node2:
    final_list.append(node2)
    node2 = node2.next

return final_list

Upvotes: 3

Views: 215

Answers (2)

Jay
Jay

Reputation: 2686

Well the way you are doing it you need indexs

so:

while i < len(list1) and j < len(list2):
  if list1[i] > list2[j]:
    n3.append(list1[i])
    i+=1
  else:
    n3.append(list2[j])
    j+=1

n3.extend(list1[i:])
n3.extend(list2[j:])

Upvotes: 1

mgilson
mgilson

Reputation: 310069

I generally do this with iterables and next:

lst1 = iter(list1)
lst2 = iter(list2)
out = sllist()
sentinel = object()
n1 = next(lst1, sentinel)
n2 = next(lst2, sentinel)
while n1 is not sentinel and n2 is not sentinel:
    if n1 > n2:
        out.append(n2)
        n2 = next(lst2, sentinel)
    elif n2 >= n1:
        out.append(n1)
        n1 = next(lst1, sentinel)
out.extend(lst1)
out.extend(lst2)

As pointed out in the comments, you could also write it as:

lst1 = iter(list1)
lst2 = iter(list2)
out = sllist()
try:
    n1 = next(lst1)
    n2 = next(lst2)
    while True:
        if n1 > n2:
            out.append(n2)
            n2 = next(lst2)
        elif n2 >= n1:
            out.append(n1)
            n1 = next(lst1)

except StopIteration:  # raised when next(...) fails.
    out.extend(lst1)
    out.extend(lst2)

It's functionally equivalent. Take your pick of whichever you like better :-)

Upvotes: 3

Related Questions