Interview Questions – Reverse Singly Linked List

Problem

Given a singly linked list containing integer keys, write an algorithm to do in-place reverse of the Singly linked list(SLL).

Example

Given the following Singly linked list

Input: 1 -> 2 -> 3 -> 4 -> 5

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

Constraints

[1] All the keys are integers

[2] 0 <= Singly Linked List_Len < 10000

Singly Linked List

SLL basically an ordered list where each node contains data & pointer to the next node. If we are at particular node, we have no way to go back to the previous node.

Solution

How to reverse the node, if we don’t have pointer to previous node in the singly linked list?

How about taking two pointers, where the first pointer keeps track of the current node and the second pointer keeps track of the next node? While we iterate through the singly linked list we keep assigning the first pointer to second pointer and keep increment the pointers

Algorithm

• Initialize the CurrentPtr = null and NextPtr = head
• while NextPtr not null
  • Keep NextPtr’s next in temp variable
  • assign NextPtr’s next to CurrentPtr
  • update currentPtr with NextPtr
  • update NextPtr with temp
• assing head to currentPtr

Main.java

import working.example.tech.InterviewQuestions.ReverseSLL;

import working.example.tech.interfaces.TestCaseRunner;
public class Main {
    public static void main(String[] args) {

        TestCaseRunner reverse = new ReverseSLL();
        reverse.RunTest();
    }
}

ReverseSLL.java

package working.example.tech.InterviewQuestions;

public class ReverseSLL implements working.example.tech.interfaces.TestCaseRunner{
    private Node head;
    public  ReverseSLL() {
        head = null;
    }
    private class Node {
        private Integer data;
        private Node next;
        Node(Integer data) {
            this.data = data;
            this.next = null;
        }
    }
    private void add(Integer data) {
        if (head == null) {
            head = new Node(data);
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new Node(data);
        }
    }

    private void reverse() {
        if (head == null || head.next == null) {
            return;
        } else {
            Node current = null;
            Node Next = head;
            while(Next != null) {
                Node temp = Next.next;
                Next.next = current;
                current = Next;
                Next = temp;
            }
            head = current;
        }
    }
    @Override
    public void RunTest() {
        this.add(10);
        this.add(5);
        this.add(30);
        this.add(50);
        this.showOut();
        this.reverse();
        this.showOut();
    }

    @Override
    public void showOut() {
        Node temp = head;
        System.out.println();
        while(temp != null) {
            System.out.print(temp.data + "-->");
            temp = temp.next;
        }
    }
}

Output

Before Reversal: 10-->5-->30-->50

After Reversal: 50-->30-->5-->10

Complexity Singly Linked List Reversal

Auxiliary space complexity: O(n)

Time complexity: O(n)

where n is the total number of singly linked list nodes

More Interview Question

https://www.workingexample.tech/interview-questions-merge-k-sorted-lists-efficiently/

https://www.workingexample.tech/interview-questions-find-the-immediate-lesser-key-than-the-given-key-in-the-binary-search-tree/

https://www.workingexample.tech/interview-questions-implement-linux-change-directory-command/