CODEWITHSUNDEEP
python-3.xlinked-list
Tariq
Tariq

Reputation: 93

Insert new value Into SortedLinked List using Python?

I implement the following code, it works but it added the new values at the end of linked list Like, [1,2,3,6], value 4 the results are [1,2,3,6,4] which is wrong the correct results is [1,2,3,4,6]

# Singly-linked lists are already defined with this interface:
class ListNode(object):
    def __init__(self, x):
        self.value = x
        self.next = None

def insertValueIntoSortedLinkedList(head, valuetoInsert):

    currentNode = head

    while currentNode is not None:
        if currentNode.next is None:
            currentNode.next = ListNode(valuetoInsert)
            return head
        currentNode = currentNode.next

My Question how to modifie the insertValueIntoSortedLinkedList function Thank you

Upvotes: 0

Views: 418

Answers (1)

Andrej Kesely
Andrej Kesely

Reputation: 195438

I made some changes to insertValueIntoSortedLinkedList(). Basically, the error is that you don't compare if the value you're going to insert is smaller than current value (so you always insert the new value to end).

# Singly-linked lists are already defined with this interface:
class ListNode(object):
    def __init__(self, x):
        self.value = x
        self.next = None

def insertValueIntoSortedLinkedList(head, valuetoInsert):
    currentNode = head
    while True:
        # is current value greater than value we are going to insert?
        if currentNode.value > valuetoInsert:
            # yes, create new node with old value
            next_node = ListNode(currentNode.value)
            next_node.next = currentNode.next

            # replace current value with new value (which is lower than old value)
            currentNode.value = valuetoInsert

            # set next node to new node we created previously (with old value)
            currentNode.next = next_node
            # we are done, return
            return

        # we are at the end, so break from while-loop
        if currentNode.next is None:
            break

        currentNode = currentNode.next

    # the valuetoInsert is greater than all values so far, so insert it to the end
    currentNode.next = ListNode(valuetoInsert)

def print_list(head):
    """ Helper method to print the list """
    currentNode = head

    while currentNode is not None:
        print(currentNode.value)
        currentNode = currentNode.next

l = ListNode(1)
insertValueIntoSortedLinkedList(l, 2)
insertValueIntoSortedLinkedList(l, 3)
insertValueIntoSortedLinkedList(l, 6)

insertValueIntoSortedLinkedList(l, 4)  # this inserts value before 6

print_list(l)

Prints:

1
2
3
4
6

Upvotes: 1

Related Questions