Merging Linked List in Python [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

I'm trying to merge two sorted linked lists. I am able to do it by creating a node every time I add an element. However, I would like to do it without creating a new node but using the old one.

This is the implementation.

from LinkedListImplementation import LinkedList


MLL = LinkedList()

LL1 = LinkedList()
LL2 = LinkedList()

array_list1 = [2, 4, 5, 7, 11, 12, 15, 20]
array_list2 = [3, 6, 9, 10]

for p in array_list1:
    LL1.addElement(p)

for q in array_list2:
    LL2.addElement(q)


while(LL1.size and LL2.size):
    e1 = LL1.Head.element
    e2 = LL2.Head.element
    if e1 < e2:
        MLL.addElement(LL1.removeElement())
    else:
        MLL.addElement(LL2.removeElement())

    if LL1.size:
        MLL.Tail.Next=LL1.Head
    else:
        MLL.Tail.Next=LL2.Head

MLL.displayLinkedList()

Below is LinkedList implementation

class LinkedList:

    class _Node:

        __slots__ = 'element', 'Next'

        def __init__(self, element, Next):
            self.element = element
            self.Next = Next


    def __init__(self):
        '''
        Constructor
        '''
        self.size = 0
        self.Head = None
        self.Tail = None

    def addElement(self, e):
        newestNode = self._Node(e, None)
        if self.size==0:
            self.Head = newestNode
            self.Tail = newestNode
        else:
            newestNode.Next=None
            self.Tail.Next=newestNode
            self.Tail=newestNode
        self.size += 1

    def removeElement(self):
        if self.size == 0:
            print "The Linked List is Empty"
        else:
            value = self.Head.element
            self.Head = self.Head.Next
            self.size -= 1
        if self.size == 0:
            self.Head = None
        return value


    def displayLinkedList(self):

        tempNode = self.Head
        while(tempNode.Next is not None):
            print "Current node element is [%d]" % tempNode.element
            print "Next node element is [%d]" % tempNode.Next.element
            tempNode = tempNode.Next
        else:
            if self.size == 1:
                print "Linked List has only element [%d]" %tempNode.element

    def isEmpty(self):
        return self.size == 0 

Answer 1

if __name__ == "__main__":
    MLL = LinkedList()

    LL1 = LinkedList()
    LL2 = LinkedList()

    array_list1 = [2, 4, 5, 7, 11, 12, 15, 20]
    array_list2 = [3, 6, 9, 10]

    for p in array_list1:
        LL1.addElement(p)

    for q in array_list2:
        LL2.addElement(q)

    cur_node_l1 = LL1.Head
    cur_node_l2 = LL2.Head
    cur_node = MLL.Head; 
    while(cur_node_l1 and cur_node_l2):
        e1 = cur_node_l1.element
        e2 = cur_node_l2.element
        if e1 < e2:
            if not cur_node:
                cur_node =  cur_node_l1;
                MLL.Head = cur_node
            else:
                cur_node.Next = cur_node_l1;
                cur_node = cur_node_l1
            cur_node_l1 = cur_node_l1.Next
#            MLL.TAIL = cur_node_l1;

        else:
            if not cur_node:
                cur_node =  cur_node_l2;
                MLL.Head = cur_node
            else:
                cur_node.Next = cur_node_l2;
                cur_node = cur_node_l2;
            cur_node_l2 = cur_node_l2.Next
#        MLL.TAIL = cur_node_l2;
    if (cur_node_l1):
        cur_node.Next = cur_node_l1
        cur_node = LL1.Tail;
    if (cur_node_l2):
        cur_node.Next = cur_node_l2
        cur_node = LL2.Tail;
    MLL.Tail = cur_node
    MLL.size = LL1.size + LL2.size
    MLL.displayLinkedList()