Merge Two Sorted Linked Lists

Write a merge function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. The merge should return the new list. The new list should be made by splicing together the nodes of the first two lists. Following is the Linked NODE and LinkedList ADT we are going to use to solve the problem. For example if the first linked list is 5->10->15 and the other linked list is 2->3->20, then merge should return a pointer to the head node of the merged list 2->3->5->10->15->20.

Node.Java

package algorithm.linkedlist;

public class Node<T> {

    T data;
    Node next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public void print() {
        String printValue = "[ " + this.data + "] ";
        if (next != null) {
            printValue += "---> ";
        }
        System.out.print(printValue);
    }
}

LinkedList.java

package algorithm.linkedlist;

public class LinkedList {

    private Node head;

    public LinkedList(Node node) {
        this.head = node;
    }

    public void add(Node node) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }
}

The merge method in TwoSortedList class is merging the two sorted list into a single sorted list. The strategy here uses a temporary dummy node as the start of the result list. The pointer Tail always points to the last node in the result list, so appending new nodes is easy.

package algorithm.linkedlist;

public class TwoSortedList {

    public Node merge(Node<Integer> head1, Node<Integer> head2) {
        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;
        Node head = new Node(0);
        Node current = head;
        while (head1 != null && head2 != null) {
            if (head1.data < head2.data) {
                current.next = head1;
                head1 = head1.next;
            } else {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }
        if (head1 != null) {
            current.next = head1;
        } else if (head2 != null) {
            current.next = head2;
        }
        return head.next;
    }
}

Now Test the algorithm by writing a main method.

package algorithm.linkedlist;

public class Test {

    public static void main(String[] args) {
        Node head = new Node(1);
        LinkedList linkedList = new LinkedList(head);
        linkedList.add(new Node(3));
        linkedList.add(new Node(5));
        linkedList.add(new Node(6));
        linkedList.add(new Node(9));

        Node head1 = new Node(2);
        LinkedList linkedList1 = new LinkedList(head1);
        linkedList1.add(new Node(4));
        linkedList1.add(new Node(7));
        linkedList1.add(new Node(8));

        TwoSortedList twoSortedList = new TwoSortedList();
        Node head3 = twoSortedList.merge(head, head1);
        LinkedListUtil.print(head3);
    }
}

Use the LinkedListUtil class to print the sorted list.

package algorithm.linkedlist;

public class LinkedListUtil {

    public static void print(Node head) {
        Node temp = head;
        while (temp != null) {
            temp.print();
            temp = temp.next;
        }
    }

    public static void newLine(){
        System.out.println();
    }
}

Output of the program is:

[ 1] ---> [ 2] ---> [ 3] ---> [ 4] ---> [ 5] ---> [ 6] ---> [ 7] ---> [ 8] ---> [ 9] 

 

core java 12 Algorithm 12 Microsoft 12

FOLLOW US ON LinkedIn



Explore Tutu'rself