Java Program to Merge Two Sorted Linked Lists

Introduction

Merging two sorted linked lists involves combining the elements of both lists into a single sorted linked list. This task is common in various algorithms, such as merge sort, and is crucial for efficiently handling sorted data. This guide will walk you through writing a Java program that merges two sorted linked lists into one.

Problem Statement

Create a Java program that:

• Implements two singly sorted linked lists.
• Merges the two sorted linked lists into a single sorted linked list.
• Displays the merged linked list.

Example:

• Input:

  • List 1: 1 -> 3 -> 5
  • List 2: 2 -> 4 -> 6

• Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

• Input:

  • List 1: 1 -> 3 -> 8
  • List 2: 2 -> 4 -> 7 -> 9

• Output: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9

Solution Steps

1. Create the Linked List and Node Structure: Define a Node class to represent each element in the linked list and a LinkedList class to manage the list.
2. Add Nodes to the Linked Lists: Implement methods to add nodes to the linked lists.
3. Merge the Two Sorted Linked Lists:

• Compare the elements of both lists.
• Append the smaller element to the merged list and move the pointer of that list forward.
• Continue until all elements from both lists are merged.

4. Display the Result: Output the merged sorted linked list.

Java Program

// Java Program to Merge Two Sorted Linked Lists // Author: https://www.rameshfadatare.com/ class Node { int data; Node next; // Constructor to initialize the node public Node(int data) { this.data = data; this.next = null; } } class LinkedList { Node head; // Method to add a new node at the end of the list public void add(int data) { Node newNode = new Node(data); if (head == null) { // Step 1: Initialize the head if the list is empty head = newNode; } else { // Step 2: Traverse to the end of the list and add the new node Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } } // Method to merge two sorted linked lists public static LinkedList mergeSortedLists(LinkedList list1, LinkedList list2) { Node dummy = new Node(0); // Step 3: Create a dummy node to simplify the merge process Node tail = dummy; Node pointer1 = list1.head; Node pointer2 = list2.head; // Step 4: Traverse both lists and append the smaller node to the merged list while (pointer1 != null && pointer2 != null) { if (pointer1.data <= pointer2.data) { tail.next = pointer1; pointer1 = pointer1.next; } else { tail.next = pointer2; pointer2 = pointer2.next; } tail = tail.next; } // Step 5: Append remaining nodes from either list (if any) if (pointer1 != null) { tail.next = pointer1; } else { tail.next = pointer2; } LinkedList mergedList = new LinkedList(); mergedList.head = dummy.next; // Step 6: The merged list's head is the next node after dummy return mergedList; } // Method to display the linked list public void display() { Node current = head; while (current != null) { System.out.print(current.data + " -> "); current = current.next; } System.out.println("null"); } } public class MergeSortedLinkedLists { public static void main(String[] args) { LinkedList list1 = new LinkedList(); LinkedList list2 = new LinkedList(); // Adding elements to the first sorted linked list list1.add(1); list1.add(3); list1.add(5); // Adding elements to the second sorted linked list list2.add(2); list2.add(4); list2.add(6); System.out.println("List 1:"); list1.display(); System.out.println("List 2:"); list2.display(); // Merging the two sorted linked lists LinkedList mergedList = LinkedList.mergeSortedLists(list1, list2); System.out.println("Merged Sorted Linked List:"); mergedList.display(); } } 

Explanation

Step 1: Initialize the Node Class

• The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.
• The constructor initializes the node with data and sets the next pointer to null.

Step 2: Initialize the LinkedList Class

• The LinkedList class manages the linked list. The class contains the head node that points to the first node in the list.
• The add() method appends a new node to the end of the list. If the list is empty, the head node is set to the new node.

Step 3: Merge Two Sorted Linked Lists

• The mergeSortedLists() method merges two sorted linked lists into one:
  • A dummy node is created to simplify the process of merging.
  • Two pointers (pointer1 and pointer2) traverse both linked lists.
  • The smaller of the two nodes pointed by pointer1 and pointer2 is appended to the merged list.
  • The pointer for the merged node’s original list is then moved forward.
  • This continues until all elements from both lists are merged.

Step 4: Append Remaining Nodes

• If one of the linked lists is exhausted before the other, the remaining nodes from the non-exhausted list are appended to the merged list.

Step 5: Return the Merged List

• The merged linked list is returned, excluding the dummy node.

Output Example

List 1: 1 -> 3 -> 5 -> null List 2: 2 -> 4 -> 6 -> null Merged Sorted Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null 

Example with Different Lists

If you add different elements to list1 and list2, such as:

list1.add(1); list1.add(3); list1.add(8); list2.add(2); list2.add(4); list2.add(7); list2.add(9); 

The output will be:

List 1: 1 -> 3 -> 8 -> null List 2: 2 -> 4 -> 7 -> 9 -> null Merged Sorted Linked List: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> null 

Conclusion

This Java program demonstrates how to merge two sorted linked lists into a single sorted linked list. The program covers essential concepts such as linked list manipulation, node traversal, and efficient merging techniques. This exercise is valuable for understanding how to manage sorted data structures and perform operations like merging in Java programming.