Merge two sorted lists

Here given code implementation process.

// C Program 
// Merge two sorted lists
#include <stdio.h>
#include <stdlib.h> //for malloc function

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
    struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create memory of head and tail Nodes
    struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
        sll->tail = NULL;
    }
    return sll;
}
// Returns a new Node of linked list
struct LinkNode *createLinkNode(int data)
{
    // Create dynamic node
    struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        // Set initial node value
        node->data = data;
        node->next = NULL;
    }
    return node;
}
// Add new Node at end of linked list 
void addNode(struct SingleLL *sll, int data)
{
    struct LinkNode *node = createLinkNode(data);
    if (sll->head == NULL)
    {
        sll->head = node;
    }
    else
    {
        // Append the node at last position
        sll->tail->next = node;
    }
    sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
    if (sll->head == NULL)
    {
        printf("\n Empty linked list\n");
        return;
    }
    struct LinkNode *temp = sll->head;
    // iterating linked list elements
    while (temp != NULL)
    {
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
// Sorted Merge of two sorted list
void mergeList(struct SingleLL *sll1, struct SingleLL *sll2)
{
    if (sll2->head == NULL)
    {
        // When have no element in second linked list
        return;
    }
    else if (sll1->head == NULL)
    {
        sll1->head = sll2->head;
        sll1->tail = sll2->tail;
    }
    else
    {
        // Define some useful resultant variable
        struct LinkNode *n1 = sll1->head;
        struct LinkNode *n2 = sll2->head;
        struct LinkNode *auxiliary = NULL;
        // Reset resultant list
        sll1->head = NULL;
        sll1->tail = NULL;
        // iterate linked list element
        while (n1 != NULL || n2 != NULL)
        {
            if (n1 != NULL && n2 != NULL)
            {
                // Compare front node element of both linked list
                if (n1->data <= n2->data)
                {
                    // Get front node of first linked list
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1->next;
                }
                else
                {
                    // Get front node of second linked list
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2->next;
                }
            }
            else if (n1 != NULL)
            {
                auxiliary = n1;
                // Visit to next node
                n1 = n1->next;
            }
            else
            {
                auxiliary = n2;
                // Visit to next node
                n2 = n2->next;
            }
            if (sll1->head == NULL)
            {
                // First node of resultant linked list
                sll1->head = auxiliary;
                sll1->tail = auxiliary;
            }
            else
            {
                // Add node at last of resultant list
                sll1->tail->next = auxiliary;
                // Set new last node
                sll1->tail = auxiliary;
            }
        }
    }
    sll2->head = NULL;
    sll2->tail = NULL;
}
int main()
{
    // Create linked list
    struct SingleLL *sll1 = newLinkedList();
    struct SingleLL *sll2 = newLinkedList();
    // Sorted linked list 1
    //  1 → 7 → 8 → 15 → 19 → NULL
    addNode(sll1, 1);
    addNode(sll1, 7);
    addNode(sll1, 8);
    addNode(sll1, 15);
    addNode(sll1, 19);
    // Sorted linked list 2
    //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    addNode(sll2, -2);
    addNode(sll2, 5);
    addNode(sll2, 6);
    addNode(sll2, 12);
    addNode(sll2, 16);
    addNode(sll2, 18);
    addNode(sll2, 19);
    addNode(sll2, 31);
    printf("\n First Linked List \n");
    display(sll1);
    printf("\n Second Linked List \n");
    display(sll2);
    mergeList(sll1, sll2);
    //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    printf("\n After Merge \n");
    display(sll1);
    return 0;
}

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
/*
  Java Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public LinkNode tail;
    public SingleLL()
    {
        this.head = null;
        this.tail = null;
    }
    //Add new Node at end of linked list 
    public void addNode(int data)
    {
        LinkNode node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            System.out.print("\n Empty linked list\n");
            return;
        }
        LinkNode temp = this.head;
        //iterating linked list elements
        while (temp != null)
        {
            System.out.print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        System.out.print(" NULL\n");
    }

    // Sorted Merge of two sorted list
    public void mergeList(SingleLL other)
    {
        if (other.head == null)
        {
            // When have no element in second linked list
            return;
        }
        else if (this.head == null)
        {
            this.head = other.head;
            this.tail = other.tail;
        }
        else
        {
            // Define some useful resultant variable
            LinkNode n1 = this.head;
            LinkNode n2 = other.head;
            LinkNode auxiliary = null;
            // Reset resultant list
            this.head = null;
            this.tail = null;
            // iterate linked list element
            while (n1 != null || n2 != null)
            {
                if (n1 != null && n2 != null)
                {
                    // Compare front node element of both linked list
                    if (n1.data <= n2.data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1.next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2.next;
                    }
                }
                else if (n1 != null)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1.next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2.next;
                }
                if (this.head == null)
                {
                    // First node of resultant linked list
                    this.head = auxiliary;
                    this.tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    this.tail.next = auxiliary;
                    // Set new last node
                    this.tail = auxiliary;
                }
            }
        }
        other.head = null;
        other.tail = null;
    }
    public static void main(String[] args)
    {
        // Create linked list
        SingleLL sll1 = new SingleLL();
        SingleLL sll2 = new SingleLL();
        // Sorted linked list 1
        //  1 → 7 → 8 → 15 → 19 → NULL
        sll1.addNode(1);
        sll1.addNode(7);
        sll1.addNode(8);
        sll1.addNode(15);
        sll1.addNode(19);
        // Sorted linked list 2
        //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
        sll2.addNode(-2);
        sll2.addNode(5);
        sll2.addNode(6);
        sll2.addNode(12);
        sll2.addNode(16);
        sll2.addNode(18);
        sll2.addNode(19);
        sll2.addNode(31);
        System.out.print("\n First Linked List \n");
        sll1.display();
        System.out.print("\n Second Linked List \n");
        sll2.display();
        sll1.mergeList(sll2);
        //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
        System.out.print("\n After Merge \n");
        sll1.display();
    }
}

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
// Include header file
#include <iostream>
using namespace std;
/*
  C++ Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode
{
    public: int data;
    LinkNode *next;
    LinkNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
class SingleLL
{
    public: LinkNode *head;
    LinkNode *tail;
    SingleLL()
    {
        this->head = NULL;
        this->tail = NULL;
    }
    //Add new Node at end of linked list
    void addNode(int data)
    {
        LinkNode *node = new LinkNode(data);
        if (this->head == NULL)
        {
            this->head = node;
        }
        else
        {
            // Append the node at last position
            this->tail->next = node;
        }
        this->tail = node;
    }
    // Display linked list element
    void display()
    {
        if (this->head == NULL)
        {
            cout << "\n Empty linked list\n";
            return;
        }
        LinkNode *temp = this->head;
        //iterating linked list elements
        while (temp != NULL)
        {
            cout << " " << temp->data << " →";
            // Visit to next node
            temp = temp->next;
        }
        cout << " NULL\n";
    }

    // Sorted Merge of two sorted list
    void mergeList(SingleLL other)
    {
        // When have no element in second linked list
        if (other.head == NULL)
        {
            return;
        }
        else if (this->head == NULL)
        {
            this->head = other.head;
            this->tail = other.tail;
        }
        else
        {
            // Define some useful resultant variable
            LinkNode *n1 = this->head;
            LinkNode *n2 = other.head;
            LinkNode *auxiliary = NULL;
            // Reset resultant list
            this->head = NULL;
            this->tail = NULL;
            // iterate linked list element
            while (n1 != NULL || n2 != NULL)
            {
                if (n1 != NULL && n2 != NULL)
                {
                    // Compare front node element of both linked list
                    if (n1->data <= n2->data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1->next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2->next;
                    }
                }
                else if (n1 != NULL)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1->next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2->next;
                }
                if (this->head == NULL)
                {
                    // First node of resultant linked list
                    this->head = auxiliary;
                    this->tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    this->tail->next = auxiliary;
                    // Set new last node
                    this->tail = auxiliary;
                }
            }
        }
        other.head = NULL;
        other.tail = NULL;
    }
};
int main()
{
    // Create linked list
    SingleLL sll1 = SingleLL();
    SingleLL sll2 = SingleLL();
    // Sorted linked list 1
    //  1 → 7 → 8 → 15 → 19 → NULL
    sll1.addNode(1);
    sll1.addNode(7);
    sll1.addNode(8);
    sll1.addNode(15);
    sll1.addNode(19);
    // Sorted linked list 2
    //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    sll2.addNode(-2);
    sll2.addNode(5);
    sll2.addNode(6);
    sll2.addNode(12);
    sll2.addNode(16);
    sll2.addNode(18);
    sll2.addNode(19);
    sll2.addNode(31);
    cout << "\n First Linked List \n";
    sll1.display();
    cout << "\n Second Linked List \n";
    sll2.display();
    sll1.mergeList(sll2);
    //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    cout << "\n After Merge \n";
    sll1.display();
    return 0;
}

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
// Include namespace system
using System;
/*
  C# Program for
  Merge two sorted lists
*/
// Linked list node
public class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public LinkNode tail;
    public SingleLL()
    {
        this.head = null;
        this.tail = null;
    }
    //Add new Node at end of linked list
    public void addNode(int data)
    {
        LinkNode node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            Console.Write("\n Empty linked list\n");
            return;
        }
        LinkNode temp = this.head;
        //iterating linked list elements
        while (temp != null)
        {
            Console.Write(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        Console.Write(" NULL\n");
    }

    // Sorted Merge of two sorted list
    public void mergeList(SingleLL other)
    {
        // When have no element in second linked list
        if (other.head == null)
        {
            return;
        }
        else if (this.head == null)
        {
            this.head = other.head;
            this.tail = other.tail;
        }
        else
        {
            // Define some useful resultant variable
            LinkNode n1 = this.head;
            LinkNode n2 = other.head;
            LinkNode auxiliary = null;
            // Reset resultant list
            this.head = null;
            this.tail = null;
            // iterate linked list element
            while (n1 != null || n2 != null)
            {
                if (n1 != null && n2 != null)
                {
                    // Compare front node element of both linked list
                    if (n1.data <= n2.data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1.next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2.next;
                    }
                }
                else if (n1 != null)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1.next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2.next;
                }
                if (this.head == null)
                {
                    // First node of resultant linked list
                    this.head = auxiliary;
                    this.tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    this.tail.next = auxiliary;
                    // Set new last node
                    this.tail = auxiliary;
                }
            }
        }
        other.head = null;
        other.tail = null;
    }
    public static void Main(String[] args)
    {
        // Create linked list
        SingleLL sll1 = new SingleLL();
        SingleLL sll2 = new SingleLL();
        // Sorted linked list 1
        //  1 → 7 → 8 → 15 → 19 → NULL
        sll1.addNode(1);
        sll1.addNode(7);
        sll1.addNode(8);
        sll1.addNode(15);
        sll1.addNode(19);
        // Sorted linked list 2
        //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
        sll2.addNode(-2);
        sll2.addNode(5);
        sll2.addNode(6);
        sll2.addNode(12);
        sll2.addNode(16);
        sll2.addNode(18);
        sll2.addNode(19);
        sll2.addNode(31);
        Console.Write("\n First Linked List \n");
        sll1.display();
        Console.Write("\n Second Linked List \n");
        sll2.display();
        sll1.mergeList(sll2);
        //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
        Console.Write("\n After Merge \n");
        sll1.display();
    }
}

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
<?php
/*
  Php Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode
{
    public $data;
    public $next;

    function __construct($data)
    {
        $this->data = $data;
        $this->next = null;
    }
}
class SingleLL
{
    public $head;
    public $tail;

    function __construct()
    {
        $this->head = null;
        $this->tail = null;
    }
    //Add new Node at end of linked list
    public  function addNode($data)
    {
        $node = new LinkNode($data);
        if ($this->head == null)
        {
            $this->head = $node;
        }
        else
        {
            // Append the node at last position
            $this->tail->next = $node;
        }
        $this->tail = $node;
    }
    // Display linked list element
    public  function display()
    {
        if ($this->head == null)
        {
            echo "\n Empty linked list\n";
            return;
        }
        $temp = $this->head;
        //iterating linked list elements
        while ($temp != null)
        {
            echo " ". $temp->data ." →";
            // Visit to next node
            $temp = $temp->next;
        }
        echo " NULL\n";
    }

    // Sorted Merge of two sorted list
    public  function mergeList($other)
    {
        // When have no element in second linked list
        if ($other->head == null)
        {
            return;
        }
        else if ($this->head == null)
        {
            $this->head = $other->head;
            $this->tail = $other->tail;
        }
        else
        {
            // Define some useful resultant variable
            $n1 = $this->head;
            $n2 = $other->head;
            $auxiliary = null;
            // Reset resultant list
            $this->head = null;
            $this->tail = null;
            // iterate linked list element
            while ($n1 != null || $n2 != null)
            {
                if ($n1 != null && $n2 != null)
                {
                    // Compare front node element of both linked list
                    if ($n1->data <= $n2->data)
                    {
                        // Get front node of first linked list
                        $auxiliary = $n1;
                        // Visit to next node
                        $n1 = $n1->next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        $auxiliary = $n2;
                        // Visit to next node
                        $n2 = $n2->next;
                    }
                }
                else if ($n1 != null)
                {
                    $auxiliary = $n1;
                    // Visit to next node
                    $n1 = $n1->next;
                }
                else
                {
                    $auxiliary = $n2;
                    // Visit to next node
                    $n2 = $n2->next;
                }
                if ($this->head == null)
                {
                    // First node of resultant linked list
                    $this->head = $auxiliary;
                    $this->tail = $auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    $this->tail->next = $auxiliary;
                    // Set new last node
                    $this->tail = $auxiliary;
                }
            }
        }
        $other->head = null;
        $other->tail = null;
    }
}

function main()
{
    // Create linked list
    $sll1 = new SingleLL();
    $sll2 = new SingleLL();
    // Sorted linked list 1
    //  1 → 7 → 8 → 15 → 19 → NULL
    $sll1->addNode(1);
    $sll1->addNode(7);
    $sll1->addNode(8);
    $sll1->addNode(15);
    $sll1->addNode(19);
    // Sorted linked list 2
    //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    $sll2->addNode(-2);
    $sll2->addNode(5);
    $sll2->addNode(6);
    $sll2->addNode(12);
    $sll2->addNode(16);
    $sll2->addNode(18);
    $sll2->addNode(19);
    $sll2->addNode(31);
    echo "\n First Linked List \n";
    $sll1->display();
    echo "\n Second Linked List \n";
    $sll2->display();
    $sll1->mergeList($sll2);
    //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    echo "\n After Merge \n";
    $sll1->display();
}
main();

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
/*
  Node Js Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode
{
    constructor(data)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    constructor()
    {
        this.head = null;
        this.tail = null;
    }
    //Add new Node at end of linked list
    addNode(data)
    {
        var node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    display()
    {
        if (this.head == null)
        {
            process.stdout.write("\n Empty linked list\n");
            return;
        }
        var temp = this.head;
        //iterating linked list elements
        while (temp != null)
        {
            process.stdout.write(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        process.stdout.write(" NULL\n");
    }

    // Sorted Merge of two sorted list
    mergeList(other)
    {
        // When have no element in second linked list
        if (other.head == null)
        {
            return;
        }
        else if (this.head == null)
        {
            this.head = other.head;
            this.tail = other.tail;
        }
        else
        {
            // Define some useful resultant variable
            var n1 = this.head;
            var n2 = other.head;
            var auxiliary = null;
            // Reset resultant list
            this.head = null;
            this.tail = null;
            // iterate linked list element
            while (n1 != null || n2 != null)
            {
                if (n1 != null && n2 != null)
                {
                    // Compare front node element of both linked list
                    if (n1.data <= n2.data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1.next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2.next;
                    }
                }
                else if (n1 != null)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1.next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2.next;
                }
                if (this.head == null)
                {
                    // First node of resultant linked list
                    this.head = auxiliary;
                    this.tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    this.tail.next = auxiliary;
                    // Set new last node
                    this.tail = auxiliary;
                }
            }
        }
        other.head = null;
        other.tail = null;
    }
}

function main()
{
    // Create linked list
    var sll1 = new SingleLL();
    var sll2 = new SingleLL();
    // Sorted linked list 1
    //  1 → 7 → 8 → 15 → 19 → NULL
    sll1.addNode(1);
    sll1.addNode(7);
    sll1.addNode(8);
    sll1.addNode(15);
    sll1.addNode(19);
    // Sorted linked list 2
    //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    sll2.addNode(-2);
    sll2.addNode(5);
    sll2.addNode(6);
    sll2.addNode(12);
    sll2.addNode(16);
    sll2.addNode(18);
    sll2.addNode(19);
    sll2.addNode(31);
    process.stdout.write("\n First Linked List \n");
    sll1.display();
    process.stdout.write("\n Second Linked List \n");
    sll2.display();
    sll1.mergeList(sll2);
    //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    process.stdout.write("\n After Merge \n");
    sll1.display();
}
main();

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
#   Python 3 Program for
#   Merge two sorted lists

#  Linked list node
class LinkNode :
    
    def __init__(self, data) :
        self.data = data
        self.next = None
    

class SingleLL :
    
    def __init__(self) :
        self.head = None
        self.tail = None
    
    # Add new Node at end of linked list 
    def addNode(self, data) :
        node = LinkNode(data)
        if (self.head == None) :
            self.head = node
        else :
            #  Append the node at last position
            self.tail.next = node
        
        self.tail = node
    
    #  Display linked list element
    def display(self) :
        if (self.head == None) :
            print("\n Empty linked list")
            return
        
        temp = self.head
        # iterating linked list elements
        while (temp != None) :
            print("", temp.data ,"→", end = "")
            #  Visit to next node
            temp = temp.next
        
        print(" NULL")
    

    #  Sorted Merge of two sorted list
    def mergeList(self, other) :
        if (other.head == None) :
            #  When have no element in second linked list
            return
        
        elif(self.head == None) :
            self.head = other.head
            self.tail = other.tail
        else :
            #  Define some useful resultant variable
            n1 = self.head
            n2 = other.head
            auxiliary = None
            #  Reset resultant list
            self.head = None
            self.tail = None
            #  iterate linked list element
            while (n1 != None or n2 != None) :
                if (n1 != None and n2 != None) :
                    #  Compare front node element of both linked list
                    if (n1.data <= n2.data) :
                        #  Get front node of first linked list
                        auxiliary = n1
                        #  Visit to next node
                        n1 = n1.next
                    else :
                        #  Get front node of second linked list
                        auxiliary = n2
                        #  Visit to next node
                        n2 = n2.next
                    
                
                elif(n1 != None) :
                    auxiliary = n1
                    #  Visit to next node
                    n1 = n1.next
                else :
                    auxiliary = n2
                    #  Visit to next node
                    n2 = n2.next
                
                if (self.head == None) :
                    #  First node of resultant linked list
                    self.head = auxiliary
                    self.tail = auxiliary
                else :
                    #  Add node at last of resultant list
                    self.tail.next = auxiliary
                    #  Set new last node
                    self.tail = auxiliary
                
            
        
        other.head = None
        other.tail = None
    

def main() :
    #  Create linked list
    sll1 = SingleLL()
    sll2 = SingleLL()
    #  Sorted linked list 1
    #   1 → 7 → 8 → 15 → 19 → NULL
    sll1.addNode(1)
    sll1.addNode(7)
    sll1.addNode(8)
    sll1.addNode(15)
    sll1.addNode(19)
    #  Sorted linked list 2
    #   -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    sll2.addNode(-2)
    sll2.addNode(5)
    sll2.addNode(6)
    sll2.addNode(12)
    sll2.addNode(16)
    sll2.addNode(18)
    sll2.addNode(19)
    sll2.addNode(31)
    print("\n First Linked List ")
    sll1.display()
    print("\n Second Linked List ")
    sll2.display()
    sll1.mergeList(sll2)
    #   -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    print("\n After Merge ")
    sll1.display()

if __name__ == "__main__": main()

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
#   Ruby Program for
#   Merge two sorted lists

#  Linked list node
class LinkNode  
    # Define the accessor and reader of class LinkNode  
    attr_reader :data, :next
    attr_accessor :data, :next
 
    
    def initialize(data) 
        self.data = data
        self.next = nil
    end

end

class SingleLL  
    # Define the accessor and reader of class SingleLL  
    attr_reader :head, :tail
    attr_accessor :head, :tail
 
    
    def initialize() 
        self.head = nil
        self.tail = nil
    end

    # Add new Node at end of linked list 
    def addNode(data) 
        node = LinkNode.new(data)
        if (self.head == nil) 
            self.head = node
        else 
            #  Append the node at last position
            self.tail.next = node
        end

        self.tail = node
    end

    #  Display linked list element
    def display() 
        if (self.head == nil) 
            print("\n Empty linked list\n")
            return
        end

        temp = self.head
        # iterating linked list elements
        while (temp != nil) 
            print(" ", temp.data ," →")
            #  Visit to next node
            temp = temp.next
        end

        print(" NULL\n")
    end


    #  Sorted Merge of two sorted list
    def mergeList(other) 
        if (other.head == nil) 
            #  When have no element in second linked list
            return
        elsif(self.head == nil) 
            self.head = other.head
            self.tail = other.tail
        else 
            #  Define some useful resultant variable
            n1 = self.head
            n2 = other.head
            auxiliary = nil
            #  Reset resultant list
            self.head = nil
            self.tail = nil
            #  iterate linked list element
            while (n1 != nil || n2 != nil) 
                if (n1 != nil && n2 != nil) 
                    #  Compare front node element of both linked list
                    if (n1.data <= n2.data) 
                        #  Get front node of first linked list
                        auxiliary = n1
                        #  Visit to next node
                        n1 = n1.next
                    else 
                        #  Get front node of second linked list
                        auxiliary = n2
                        #  Visit to next node
                        n2 = n2.next
                    end

                elsif(n1 != nil) 
                    auxiliary = n1
                    #  Visit to next node
                    n1 = n1.next
                else 
                    auxiliary = n2
                    #  Visit to next node
                    n2 = n2.next
                end

                if (self.head == nil) 
                    #  First node of resultant linked list
                    self.head = auxiliary
                    self.tail = auxiliary
                else 
                    #  Add node at last of resultant list
                    self.tail.next = auxiliary
                    #  Set new last node
                    self.tail = auxiliary
                end

            end

        end

        other.head = nil
        other.tail = nil
    end

end

def main() 
    #  Create linked list
    sll1 = SingleLL.new()
    sll2 = SingleLL.new()
    #  Sorted linked list 1
    #   1 → 7 → 8 → 15 → 19 → NULL
    sll1.addNode(1)
    sll1.addNode(7)
    sll1.addNode(8)
    sll1.addNode(15)
    sll1.addNode(19)
    #  Sorted linked list 2
    #   -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    sll2.addNode(-2)
    sll2.addNode(5)
    sll2.addNode(6)
    sll2.addNode(12)
    sll2.addNode(16)
    sll2.addNode(18)
    sll2.addNode(19)
    sll2.addNode(31)
    print("\n First Linked List \n")
    sll1.display()
    print("\n Second Linked List \n")
    sll2.display()
    sll1.mergeList(sll2)
    #   -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    print("\n After Merge \n")
    sll1.display()
end

main()

Output

 First Linked List 
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List 
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge 
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
/*
  Scala Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
    def this(data: Int)
    {
        this(data, null);
    }
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
    def this()
    {
        this(null, null);
    }
    //Add new Node at end of linked list
    def addNode(data: Int): Unit = {
        var node: LinkNode = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    def display(): Unit = {
        if (this.head == null)
        {
            print("\n Empty linked list\n");
            return;
        }
        var temp: LinkNode = this.head;
        //iterating linked list elements
        while (temp != null)
        {
            print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        print(" NULL\n");
    }

    // Sorted Merge of two sorted list
    def mergeList(other: SingleLL): Unit = {
        // When have no element in second linked list
        if (other.head == null)
        {
            return;
        }
        else if (this.head == null)
        {
            this.head = other.head;
            this.tail = other.tail;
        }
        else
        {
            // Define some useful resultant variable
            var n1: LinkNode = this.head;
            var n2: LinkNode = other.head;
            var auxiliary: LinkNode = null;
            // Reset resultant list
            this.head = null;
            this.tail = null;
            // iterate linked list element
            while (n1 != null || n2 != null)
            {
                if (n1 != null && n2 != null)
                {
                    // Compare front node element of both linked list
                    if (n1.data <= n2.data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1.next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2.next;
                    }
                }
                else if (n1 != null)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1.next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2.next;
                }
                if (this.head == null)
                {
                    // First node of resultant linked list
                    this.head = auxiliary;
                    this.tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    this.tail.next = auxiliary;
                    // Set new last node
                    this.tail = auxiliary;
                }
            }
        }
        other.head = null;
        other.tail = null;
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        // Create linked list
        var sll1: SingleLL = new SingleLL();
        var sll2: SingleLL = new SingleLL();
        // Sorted linked list 1
        //  1 → 7 → 8 → 15 → 19 → NULL
        sll1.addNode(1);
        sll1.addNode(7);
        sll1.addNode(8);
        sll1.addNode(15);
        sll1.addNode(19);
        // Sorted linked list 2
        //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
        sll2.addNode(-2);
        sll2.addNode(5);
        sll2.addNode(6);
        sll2.addNode(12);
        sll2.addNode(16);
        sll2.addNode(18);
        sll2.addNode(19);
        sll2.addNode(31);
        print("\n First Linked List \n");
        sll1.display();
        print("\n Second Linked List \n");
        sll2.display();
        sll1.mergeList(sll2);
        //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
        print("\n After Merge \n");
        sll1.display();
    }
}

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
/*
  Swift 4 Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.next = nil;
    }
}
class SingleLL
{
    var head: LinkNode? ;
    var tail: LinkNode? ;
    init()
    {
        self.head = nil;
        self.tail = nil;
    }
    //Add new Node at end of linked list
    func addNode(_ data: Int)
    {
        let node: LinkNode? = LinkNode(data);
        if (self.head == nil)
        {
            self.head = node;
        }
        else
        {
            // Append the node at last position
            self.tail!.next = node;
        }
        self.tail = node;
    }
    // Display linked list element
    func display()
    {
        if (self.head == nil)
        {
            print("\n Empty linked list");
            return;
        }
        var temp: LinkNode? = self.head;
        //iterating linked list elements
        while (temp  != nil)
        {
            print("", temp!.data ,"→", terminator: "");
            // Visit to next node
            temp = temp!.next;
        }
        print(" NULL");
    }

    // Sorted Merge of two sorted list
    func mergeList(_ other: SingleLL? )
    {
        // When have no element in second linked list
        if (other!.head == nil)
        {
            return;
        }
        else if (self.head == nil)
        {
            self.head = other!.head;
            self.tail = other!.tail;
        }
        else
        {
            // Define some useful resultant variable
            var n1: LinkNode? = self.head;
            var n2: LinkNode? = other!.head;
            var auxiliary: LinkNode? = nil;
            // Reset resultant list
            self.head = nil;
            self.tail = nil;
            // iterate linked list element
            while (n1  != nil || n2  != nil)
            {
                if (n1  != nil && n2  != nil)
                {
                    // Compare front node element of both linked list
                    if (n1!.data <= n2!.data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1!.next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2!.next;
                    }
                }
                else if (n1  != nil)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1!.next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2!.next;
                }
                if (self.head == nil)
                {
                    // First node of resultant linked list
                    self.head = auxiliary;
                    self.tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    self.tail!.next = auxiliary;
                    // Set new last node
                    self.tail = auxiliary;
                }
            }
        }
        other!.head = nil;
        other!.tail = nil;
    }
}
func main()
{
    // Create linked list
    let sll1: SingleLL = SingleLL();
    let sll2: SingleLL = SingleLL();
    // Sorted linked list 1
    //  1 → 7 → 8 → 15 → 19 → NULL
    sll1.addNode(1);
    sll1.addNode(7);
    sll1.addNode(8);
    sll1.addNode(15);
    sll1.addNode(19);
    // Sorted linked list 2
    //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    sll2.addNode(-2);
    sll2.addNode(5);
    sll2.addNode(6);
    sll2.addNode(12);
    sll2.addNode(16);
    sll2.addNode(18);
    sll2.addNode(19);
    sll2.addNode(31);
    print("\n First Linked List ");
    sll1.display();
    print("\n Second Linked List ");
    sll2.display();
    sll1.mergeList(sll2);
    //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    print("\n After Merge ");
    sll1.display();
}
main();

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
/*
  Kotlin Program for
  Merge two sorted lists
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    var head: LinkNode ? ;
    var tail: LinkNode ? ;
    constructor()
    {
        this.head = null;
        this.tail = null;
    }
    //Add new Node at end of linked list
    fun addNode(data: Int): Unit
    {
        var node: LinkNode ? = LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail?.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    fun display(): Unit
    {
        if (this.head == null)
        {
            print("\n Empty linked list\n");
            return;
        }
        var temp: LinkNode ? = this.head;
        //iterating linked list elements
        while (temp != null)
        {
            print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        print(" NULL\n");
    }

    // Sorted Merge of two sorted list
    fun mergeList(other: SingleLL): Unit
    {
        // When have no element in second linked list
        if (other.head == null)
        {
            return;
        }
        else if (this.head == null)
        {
            this.head = other.head;
            this.tail = other.tail;
        }
        else
        {
            // Define some useful resultant variable
            var n1: LinkNode ? = this.head;
            var n2: LinkNode ? = other.head;
            var auxiliary: LinkNode ? ;
            // Reset resultant list
            this.head = null;
            this.tail = null;
            // iterate linked list element
            while (n1 != null || n2 != null)
            {
                if (n1 != null && n2 != null)
                {
                    // Compare front node element of both linked list
                    if (n1.data <= n2.data)
                    {
                        // Get front node of first linked list
                        auxiliary = n1;
                        // Visit to next node
                        n1 = n1.next;
                    }
                    else
                    {
                        // Get front node of second linked list
                        auxiliary = n2;
                        // Visit to next node
                        n2 = n2.next;
                    }
                }
                else if (n1 != null)
                {
                    auxiliary = n1;
                    // Visit to next node
                    n1 = n1.next;
                }
                else
                {
                    auxiliary = n2;
                    // Visit to next node
                    n2 = n2?.next;
                }
                if (this.head == null)
                {
                    // First node of resultant linked list
                    this.head = auxiliary;
                    this.tail = auxiliary;
                }
                else
                {
                    // Add node at last of resultant list
                    this.tail?.next = auxiliary;
                    // Set new last node
                    this.tail = auxiliary;
                }
            }
        }
        other.head = null;
        other.tail = null;
    }
}
fun main(args: Array < String > ): Unit
{
    // Create linked list
    var sll1: SingleLL = SingleLL();
    var sll2: SingleLL = SingleLL();
    // Sorted linked list 1
    //  1 → 7 → 8 → 15 → 19 → NULL
    sll1.addNode(1);
    sll1.addNode(7);
    sll1.addNode(8);
    sll1.addNode(15);
    sll1.addNode(19);
    // Sorted linked list 2
    //  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
    sll2.addNode(-2);
    sll2.addNode(5);
    sll2.addNode(6);
    sll2.addNode(12);
    sll2.addNode(16);
    sll2.addNode(18);
    sll2.addNode(19);
    sll2.addNode(31);
    print("\n First Linked List \n");
    sll1.display();
    print("\n Second Linked List \n");
    sll2.display();
    sll1.mergeList(sll2);
    //  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
    print("\n After Merge \n");
    sll1.display();
}

Output

 First Linked List
 1 → 7 → 8 → 15 → 19 → NULL

 Second Linked List
 -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

 After Merge
 -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved