Concatenation of Two Linked Lists in Java — Step by Step Explanation

In this article, we will learn how to concatenate two linked lists in Java step by step.

Concatenation means joining two linked lists together so that the last node of the first list points to the first node of the second list.

---

What is Concatenation of Linked Lists?

Suppose we have two linked lists:

List 1: 2 -> 4 -> 6 -> NULL
List 2: 8 -> 10 -> 12 -> NULL

After concatenation:

2 -> 4 -> 6 -> 8 -> 10 -> 12 -> NULL

The last node of the first list becomes connected to the first node of the second list.

---

Algorithm to Concatenate Two Linked Lists

1. ptr = startL

2. Repeat until ptr = NULL
3. save = ptr
4. ptr = ptr.LINK

5. save.LINK = startM

Explanation

• ptr traverses the first list
• save stores the last node of the first list
• The link of the last node is connected to the start of the second list

---

Step 1: Understanding the Node Class

Each node contains:

• data — stores the value
• link — stores the address of the next node

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class TestNode {

    public static void main(String[] args) {

        Node n = new Node(10);

        System.out.println("Data: " + n.data);
        System.out.println("Link: " + n.link);
    }
}

---

Step 2: Creating a Linked List

A linked list starts from a reference variable called start.

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    LinkedList() {
        start = null;
    }

    boolean isEmpty() {
        return start == null;
    }
}

class TestList {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        if (list.isEmpty()) {
            System.out.println("List is empty");
        }
    }
}

---

Step 3: Inserting Nodes into the Linked List

Before concatenation, we need to create two linked lists.

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void display() {

        Node ptr = start;

        while (ptr != null) {

            System.out.print(ptr.data + " -> ");

            ptr = ptr.link;
        }

        System.out.println("NULL");
    }
}

class TestInsert {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);

        list.display();
    }
}

Output

10 -> 20 -> 30 -> NULL

---

Step 4: Traversing the Linked List

Traversal means visiting each node one by one.

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void traverse() {

        Node ptr = start;

        while (ptr.link != null) {

            System.out.print(ptr.data + " -> ");

            ptr = ptr.link;
        }

        System.out.println(ptr.data + " !!!!");
    }
}

class TestTraverse {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.insertAtEnd(2);
        list.insertAtEnd(4);
        list.insertAtEnd(6);

        list.traverse();
    }
}

Output

2 -> 4 -> 6 !!!!

---

Step 5: Understanding Concatenation Logic

Now let us join two linked lists.

Suppose:

List 1:
2 -> 4 -> 6 -> NULL

List 2:
8 -> 10 -> 12 -> NULL

After concatenation:

2 -> 4 -> 6 -> 8 -> 10 -> 12 -> NULL

The last node of List 1 should point to the first node of List 2.

---

Step 6: Basic Concatenation Program

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void concat(Node secondListStart) {

        Node ptr = start;
        Node save = null;

        while (ptr != null) {

            save = ptr;

            ptr = ptr.link;
        }

        save.link = secondListStart;
    }

    void traverse() {

        Node ptr = start;

        while (ptr != null) {

            System.out.print(ptr.data + " -> ");

            ptr = ptr.link;
        }

        System.out.println("NULL");
    }
}

class TestConcat {

    public static void main(String[] args) {

        LinkedList list1 = new LinkedList();
        LinkedList list2 = new LinkedList();

        list1.insertAtEnd(2);
        list1.insertAtEnd(4);
        list1.insertAtEnd(6);

        list2.insertAtEnd(8);
        list2.insertAtEnd(10);
        list2.insertAtEnd(12);

        list1.concat(list2.start);

        list1.traverse();
    }
}

Output

2 -> 4 -> 6 -> 8 -> 10 -> 12 -> NULL

---

Step 7: Complete Concatenation Program

This complete program creates two linked lists and then concatenates them.

import java.io.*;

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    LinkedList() {
        start = null;
    }

    boolean isEmpty() {
        return start == null;
    }

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void traverse() {

        Node ptr = start;

        while (ptr.link != null) {

            System.out.print(ptr.data + " -> ");

            ptr = ptr.link;
        }

        System.out.println(ptr.data + " !!!!");
    }

    void concat(Node secondListStart) {

        Node ptr = start;
        Node save = null;

        while (ptr != null) {

            save = ptr;

            ptr = ptr.link;
        }

        save.link = secondListStart;
    }
}

class LinkedListTest {

    public static void main(String[] args) throws IOException {

        int num;

        LinkedList L1 = new LinkedList();
        LinkedList L2 = new LinkedList();

        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));

        System.out.println("Starting List Test for CONCATENATION");

        System.out.println("Enter 7 integers for List ONE");

        for (int i = 0; i < 7; i++) {

            num = Integer.parseInt(br.readLine());

            L1.insertAtEnd(num);
        }

        System.out.println("\nList ONE is:");

        L1.traverse();

        System.out.println("\nEnter 5 integers for List TWO");

        for (int i = 0; i < 5; i++) {

            num = Integer.parseInt(br.readLine());

            L2.insertAtEnd(num);
        }

        System.out.println("\nList TWO is:");

        L2.traverse();

        L1.concat(L2.start);

        System.out.println("\nConcatenated List is:");

        L1.traverse();

        System.out.println("\nList Test Over");
    }
}

Sample Output

Starting List Test for CONCATENATION

Enter 7 integers for List ONE

4
56
76
3
2
6
2

List ONE is:

2 -> 2 -> 3 -> 4 -> 6 -> 56 -> 76 !!!!

Enter 5 integers for List TWO

6
3
4
8
20

List TWO is:

3 -> 4 -> 6 -> 8 -> 20 !!!!

Concatenated List is:

2 -> 2 -> 3 -> 4 -> 6 -> 56 -> 76 ->
3 -> 4 -> 6 -> 8 -> 20 !!!!

List Test Over

---

How Concatenation Works

Suppose:

List 1:
A -> B -> C -> NULL

List 2:
W -> X -> Y -> Z -> NULL

During concatenation:

• The last node of List 1 is found
• The last node’s link is changed
• It points to the start of List 2

Final result:

A -> B -> C -> W -> X -> Y -> Z -> NULL

---

Important Concepts Used

• Linked list traversal
• Finding the last node
• Updating links
• Joining two linked lists
• Pointer manipulation

---

Recommended Teaching Sequence

1. Explain node structure
2. Create first linked list
3. Create second linked list
4. Traverse both lists
5. Find the last node of first list
6. Connect last node to second list
7. Display the concatenated list

---

Key Learning

Concatenation combines two linked lists into a single linked list.

Instead of copying elements, concatenation works by changing the link of the last node of the first list.

This operation is efficient because only one link needs to be updated.