Reversal of a Linked List in Java — Complete Explanation

Reversal of a linked list means changing the order of the nodes so that the last node becomes the first node and the first node becomes the last node.

---

What is Reversal of a Linked List?

Suppose we have the following linked list:

5 -> 7 -> 10 -> 12 -> NULL

After reversing:

12 -> 10 -> 7 -> 5 -> NULL

The direction of the list becomes completely opposite.

---

Two Methods of Reversing a Linked List

There are mainly two methods:

1. Method 1: Creating a New Reversed List
2. Method 2: Reversing the Nodes of the Same List

---

Method 1: Creating a New Reversed List

In this method:

• We traverse the original list
• Create new nodes
• Insert each node at the beginning of a new list

---

Example of Method 1

Original List

5 -> 7 -> 10 -> 12 -> NULL

---

Step 1

Insert 5 into new list:

5 -> NULL

---

Step 2

Insert 7 at the beginning:

7 -> 5 -> NULL

---

Step 3

Insert 10 at the beginning:

10 -> 7 -> 5 -> NULL

---

Step 4

Insert 12 at the beginning:

12 -> 10 -> 7 -> 5 -> NULL

Now the list is completely reversed.

---

Algorithm to Reverse a List — Method 1

1. If List is empty
2. Print "List Empty"
3. Exit

4. fp = start
5. newlist.start = NULL

6. Repeat until fp != NULL

7. Create new node nptr
8. nptr.info = fp.info
9. nptr.next = NULL

10. If newlist is empty
11. newlist.start = nptr

12. Else
13. nptr.next = newlist.start
14. newlist.start = nptr

15. fp = fp.next

16. END

---

Method 2: Reversing the Same List

In this method:

• No new list is created
• We swap node values
• First node swaps with last node
• Second node swaps with second-last node

---

Example of Method 2

Original List

5 -> 7 -> 10 -> 12 -> NULL

---

Swap First and Last

12 -> 7 -> 10 -> 5 -> NULL

---

Swap Second and Second Last

12 -> 10 -> 7 -> 5 -> NULL

The linked list is now reversed.

---

Algorithm to Reverse a List — Method 2

1. If start = NULL
2. Print "List Empty"
3. Exit

4. fp = start
5. lp = NULL

6. Repeat n/2 times

7. save = ptr = start

8. Repeat until ptr = lp

9. save = ptr
10. ptr = ptr.next

11. lp = save

12. temp = fp.info
13. fp.info = lp.info
14. lp.info = temp

15. fp = fp.next

16. END

---

Step 1: Creating the Node Class

class Node {

    int data;
    Node link;

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

---

Step 2: Creating the Linked List

class LinkedList {

    Node start;

    LinkedList() {
        start = null;
    }

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

---

Step 3: Insertion Program

We first create the linked list before reversing.

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;
}

---

Step 4: Traversal Program

Traversal is used to display all nodes.

void traverse() {

    Node ptr = start;

    while(ptr != null) {

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

        ptr = ptr.link;
    }

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

---

Step 5: Reversing by Creating a New List

void reverseNew(LinkedList revList) {

    revList.start = null;

    Node ptr = start;

    while(ptr != null) {

        Node nptr = new Node(ptr.data);

        nptr.link = revList.start;

        revList.start = nptr;

        ptr = ptr.link;
    }
}

---

Explanation

• Create a new node
• Insert it at the beginning
• Move to next node

This automatically reverses the order.

---

Step 6: Reversing the Same List

void reverseSameList() {

    int size = 0;

    Node temp = start;

    while(temp != null) {

        size++;

        temp = temp.link;
    }

    Node fp = start;

    for(int i = 0; i < size / 2; i++) {

        Node ptr = start;
        Node save = start;
        Node lp = null;

        while(ptr != lp) {

            save = ptr;

            ptr = ptr.link;
        }

        lp = save;

        int t = fp.data;

        fp.data = lp.data;

        lp.data = t;

        fp = fp.link;
    }
}

---

Complete Program to Reverse a Linked List

import java.io.*;

class Node {

    int data;
    Node link;

    Node(int d) {

        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    LinkedList() {

        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 != null) {

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

            ptr = ptr.link;
        }

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

    void reverseNew(LinkedList revList) {

        revList.start = null;

        Node ptr = start;

        while(ptr != null) {

            Node nptr = new Node(ptr.data);

            nptr.link = revList.start;

            revList.start = nptr;

            ptr = ptr.link;
        }
    }

    void reverseSameList() {

        int size = 0;

        Node temp = start;

        while(temp != null) {

            size++;

            temp = temp.link;
        }

        int[] arr = new int[size];

        temp = start;

        int i = 0;

        while(temp != null) {

            arr[i] = temp.data;

            temp = temp.link;

            i++;
        }

        temp = start;

        for(i = size - 1; i >= 0; i--) {

            temp.data = arr[i];

            temp = temp.link;
        }
    }
}

class ReverseTest {

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

        LinkedList list = new LinkedList();

        LinkedList revList = new LinkedList();

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

        System.out.println(
                "Enter 7 integers");

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

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

            list.insertAtEnd(num);
        }

        System.out.println("\nOriginal List:");

        list.traverse();

        list.reverseNew(revList);

        System.out.println(
                "\nReversed New List:");

        revList.traverse();

        System.out.println(
                "\nOriginal List Remains Same:");

        list.traverse();

        list.reverseSameList();

        System.out.println(
                "\nOriginal List After Reversal:");

        list.traverse();
    }
}

---

Sample Output

Enter 7 integers

7
8
5
4
3
5
2

Original List:

2 -> 3 -> 4 -> 5 -> 5 -> 7 -> 8 -> NULL

Reversed New List:

8 -> 7 -> 5 -> 5 -> 4 -> 3 -> 2 -> NULL

Original List Remains Same:

2 -> 3 -> 4 -> 5 -> 5 -> 7 -> 8 -> NULL

Original List After Reversal:

8 -> 7 -> 5 -> 5 -> 4 -> 3 -> 2 -> NULL

---

Difference Between the Two Methods

Method 1	Method 2
Creates a new list	Uses the same list
Needs extra memory	No extra list required
Easy to understand	More complex
Original list remains unchanged	Original list changes

---

Important Concepts Used

• Linked list traversal
• Pointer manipulation
• Insertion at beginning
• Node swapping
• List reversal techniques

---

Teaching Sequence Recommendation

1. Explain linked list structure
2. Create nodes
3. Insert nodes
4. Traverse list
5. Explain Method 1 reversal
6. Explain Method 2 reversal
7. Compare both methods
8. Run complete program

---

Key Learning

Reversal of a linked list changes the order of nodes from beginning-to-end into end-to-beginning.

This can be done:

• By creating a new reversed list
• Or by reversing nodes of the same list

Linked list reversal is one of the most important operations in Data Structures.