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

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

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.

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.

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.

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] 

Categories: Linked List

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s