Splitting a Linked List in Java — Step by Step Explanation

In this article, we will learn how to split a linked list into two separate linked lists in Java.

Splitting means breaking one linked list into two smaller linked lists from a specified node position.

---

What is Splitting of a Linked List?

Suppose we have the following linked list:

T -> E -> S -> T -> I -> N -> G -> NULL

If we split the list from the 4th node:

• The first list becomes:

T -> E -> S -> NULL

• The second list becomes:

T -> I -> N -> G -> NULL

The original linked list is divided into two independent linked lists.

---

Algorithm to Split a Linked List into Two Lists

1. ptr = start
2. save = start
3. ctr = 1

4. Repeat until ctr < n and ptr != NULL

5. save = ptr
6. ptr = ptr.LINK
7. ctr = ctr + 1

8. If ptr = NULL
9. Print "No such node exists"

10. Else
11. startN = ptr
12. save.LINK = NULL

13. END

Explanation

• ptr moves node by node
• save stores the previous node
• When the split position is reached:
  • The second list starts from ptr
  • The previous node link becomes NULL

---

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 splitting, we need to create a linked list.

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 Splitting Logic

Suppose we have:

2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

If we split from node position 4:

First list:

2 -> 3 -> 4 -> 5

Second list:

6 -> 7 -> 8 -> 9

The link after node 5 becomes NULL.

---

Step 6: Basic Splitting 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 split(LinkedList L1, LinkedList L2) {

        Node ptr;
        Node save;

        L1.start = start;

        save = ptr = start;

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

            save = ptr;

            ptr = ptr.link;
        }

        save.link = null;

        L2.start = ptr;
    }

    void traverse() {

        Node ptr = start;

        while (ptr != null) {

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

            ptr = ptr.link;
        }

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

class TestSplit {

    public static void main(String[] args) {

        LinkedList mainList = new LinkedList();

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

        mainList.insertAtEnd(2);
        mainList.insertAtEnd(3);
        mainList.insertAtEnd(4);
        mainList.insertAtEnd(5);
        mainList.insertAtEnd(6);
        mainList.insertAtEnd(7);

        mainList.split(L1, L2);

        System.out.println("First List:");
        L1.traverse();

        System.out.println("Second List:");
        L2.traverse();
    }
}

Output

First List:
2 -> 3 -> 4 -> 5 -> NULL

Second List:
6 -> 7 -> NULL

---

Step 7: Complete Program to Split a Linked List

This complete program creates one linked list and splits it into two lists.

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 split(LinkedList L1, LinkedList L2)
            throws IOException {

        Node ptr;
        Node save;

        System.out.print(
                "Enter the node number from where "
                        + "the list is to be split: ");

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

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

        if (num <= 0 || num > 10) {

            System.out.println(
                    "Invalid node number. Can't Split!!!");
        }
        else {

            L1.start = start;

            save = ptr = start;

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

                save = ptr;

                ptr = ptr.link;
            }

            save.link = null;

            L2.start = ptr;
        }
    }
}

class LinkedListTest {

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

        int num;

        LinkedList mainList = new LinkedList();

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

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

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

        System.out.println(
                "Enter 10 integers for MAIN list");

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

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

            mainList.insertAtEnd(num);
        }

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

        mainList.traverse();

        mainList.split(L1, L2);

        System.out.println("\nSplit lists are:");

        L1.traverse();

        L2.traverse();

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

Sample Output

Starting List Test for SPLITTING

Enter 10 integers for MAIN list

5
6
7
2
3
4
9
8
6
5

MAIN List is:

2 -> 3 -> 4 -> 5 -> 5 -> 6 -> 6 -> 7 -> 8 -> 9 !!!!

Enter the node number from where the list is to be split:

4

Split lists are:

2 -> 3 -> 4 -> 5 !!!!

5 -> 6 -> 6 -> 7 -> 8 -> 9 !!!!

List Test Over

---

How Splitting Works

Suppose the linked list is:

A -> B -> C -> D -> E -> F -> NULL

If we split after node C:

First list:

A -> B -> C -> NULL

Second list:

D -> E -> F -> NULL

The link of node C becomes NULL.

---

Important Concepts Used

• Linked list traversal
• Pointer manipulation
• Breaking links between nodes
• Creating two independent linked lists
• Using multiple linked list objects

---

Recommended Teaching Sequence

1. Explain linked list structure
2. Create a linked list
3. Insert nodes into the list
4. Traverse the list
5. Find the split position
6. Break the link using NULL
7. Create second list
8. Display both split lists

---

Key Learning

Splitting a linked list means dividing one linked list into two smaller linked lists.

This is done by:

• Finding the split position
• Breaking the link at that position
• Creating a new start pointer for the second list

The original list becomes two separate linked lists after splitting.