Java Program to Merge two lists

May 30, 2023

What is LinkedList ?

In this Article, We will going to write a Program to Merge two lists.

A linked list is a linear data structure in which each element (called a node) stores a reference to the next element in the list. Linked lists are dynamic data structures, which means that their size can change during the execution of a program. In contrast, arrays have a fixed size, which means that you need to specify the size of the array when you create it and you cannot change it later.

Algorithm to Merge two LinkedList:

Create a new empty linked list that will store the merged result.
Traverse both the input linked lists in parallel, starting from their heads.
Compare the values of the current nodes in both the lists.
Append the smaller value node to the merged linked list.
Move the pointer of the merged linked list to the last node added.
Move the pointer of the linked list from which the node was added to its next node.
Repeat steps 3-6 until both input linked lists are completely traversed.
Append the remaining nodes of the non-empty linked list to the end of the merged linked list.
Return the merged linked list.

Program to Merge Two LinkedList:

Run

import java.util.LinkedList;

public class Main {
    public static LinkedList< Integer > merge(LinkedList< Integer > l1, LinkedList< Integer > l2) {
        LinkedList< Integer > result = new LinkedList<>();
        int i = 0, j = 0;

        // Traverse both linked lists and compare their values
        while (i < l1.size() && j < l2.size()) {
            if (l1.get(i) < l2.get(j)) {
                result.add(l1.get(i));
                i++;
            } else {
                result.add(l2.get(j));
                j++;
            }
        }

        // Add any remaining elements of the first linked list
        while (i < l1.size()) {
            result.add(l1.get(i));
            i++;
        }

        // Add any remaining elements of the second linked list
        while (j < l2.size()) {
            result.add(l2.get(j));
            j++;
        }

        return result;
    }

    public static void main(String[] args) {
        LinkedList< Integer > l1 = new LinkedList<>();
        LinkedList< Integer > l2 = new LinkedList<>();

        l1.add(1);
        l1.add(3);
        l1.add(5);

        l2.add(2);
        l2.add(4);
        l2.add(6);

        LinkedList< Integer > result = merge(l1, l2);
        System.out.println(result);
    }
}

Output:

[1, 2, 3, 4, 5, 6]

Explanation: In the above program, the merge() method takes two LinkedLists l1 and l2 as input and returns a new LinkedList that is the result of merging the two input lists. The algorithm used is the same as the one described in the previous answer. In the main() method, we create two LinkedLists l1 and l2, add some elements to them, and call the merge() method to merge them. Finally, we print the merged list using the System.out.println() statement.

Java Program to Merge Two LinkedList Using addAll() Function:

Run

import java.util.ArrayList;
import java.util.List;

public class Main{
    public static void main(String[] args) {
        List list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);

        List list2 = new ArrayList<>();
        list2.add(4);
        list2.add(5);
        list2.add(6);

        // create a new list that contains all the elements of list1
        List mergedList = new ArrayList<>(list1);
        
        // add all the elements of list2 to the mergedList
        mergedList.addAll(list2);  

        System.out.println("Merged List: " + mergedList);
    }
}

Output:

Merged List: [1, 2, 3, 4, 5, 6]

Explanation: In the above program, we create two ArrayLists list1 and list2, add some elements to them, and then create a new ArrayList mergedList that contains all the elements of list1. We then use the addAll() method to add all the elements of list2 to mergedList.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others