Linked List Data Structure

➤ Java Bean with Examples
➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program

Linked List Data Structure | A Linked List can used in the place of the array. There are some limitations of array data structure:-

  1. Either size is fixed and pre-allocated (in both fixed and variable size arrays like ArrayList/Vector), or the worst-case insertion at the end is Θ(n).
  2. Insertion or deletion in the middle and beginning is costly.
  3. Implementation of data structures like queue and deque is complex with arrays.

Table of Contents

Consider a sequence of items are given. Whenever we see an item x in the sequence, we need to replace it with 5 instance of another item y.
I/P: d e a x q r x p y
O/P: d e a y y y y y q r y y y y y p y

Using array, we have to create temporary array multiple times to copy the item and inserting the new item. It will take extra space. Whereas in Linked List we don’t need extra space, and because we don’t have to copy the array everytime.

In system level programming, where memory is limited, we can’t allocated large array. Instead linked list can be used.

The idea is to drop the continuous memory requirement so that insertion, deletion can efficiently happen at the middle also and no need to pre-allocate the space (no extra nodes).

Single Linked List Implementation

10 => 5 => 20 => 25 => null
Here 10 is head.

Simple Linked List Implementation In Java

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.next = temp2;
    }
}

class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null; // optional
    }
}

In Java, next = null; this line inside Node() constructor is optional because the default value for any object is null. Problem: Array to LinkedList

a. Print Elements

Traversing a singly Linked List In Java

// using while loop
private static void printList(Node head) {
    Node curr = head;
    while (curr != null) {
        System.out.print(curr.data + " ");
        curr = curr.next;
    }
    System.out.println();
}
// using for loop
private static void printList(Node head) {
    for (Node curr = head; curr != null; curr = curr.next) {
        System.out.print(curr.data + " ");
    }
    System.out.println();
}

In main() method:- printList(head);

Output:-
10 20 30

Time complexity: O(n), auxiliary space: O(1)

Recursive Display of Linked List

private static void recursivePrint(Node head) {
    if (head == null) {
        return;
    }
    System.out.print(head.data + " ");
    recursivePrint(head.next);
}

In main method:- recursivePrint(head);

Time complexity: O(n), auxiliary space: O(n)
Problem: Count Nodes in LinkedList

b. Insert in Single Linked List

1. Insert at the beginning of Singly Linked List

Initial linked List: 10 => 20 => 30 => null
Item to insert => 5
Output: 5 => 10 => 20 => 30 => null

Initial linked List: null
Item to insert => 5
Output: 5 => null

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.next = temp2;
        printList(head);

        head = insertAtBegining(head, 5);
        printList(head);
    }

    private static Node insertAtBegining(Node head, int k) {
        Node node = new Node(k);
        node.next = head;
        return node;
    }

    // printList()
}

2. Insert at the End of Singly Linked List

Initial linked List: 10 => 20 => 30 => null
Item to insert => 5
Output: 10 => 20 => 30 => 5
Problem

Initial linked List: null
Item to insert => 5
Output: 5 => null

private static Node insertEnd(Node head, int item) {
    Node temp = new Node(item);

    // case when list is empty
    if (head == null) {
        return temp;
    }

    // move to the last node
    Node curr = head;
    while (curr.next != null) {
        curr = curr.next;
    }

    // assign
    curr.next = temp;
    return head;
}

3. Insert at Given Position in Singly Linked List

Initial linked List: 10 => 30 => 50 => 70 => null
Insert 20 at 2nd position
Output: 10 => 20 => 30 => 50 => 70 => null

Initial linked List: 10 => 30 => 50 => 70 => null
Insert 80 at 5th position
Output: 10 => 30 => 50 => 70 => 80 => null

Initial linked List: 10 => 20 => null
Insert 30 at 4th position
Output: 10 => 20 => null
Position is not valid

We can insert the element in a valid position. If the given position is > list_size + 1 then we can’t insert the given data.

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.next = temp2;
        printList(head);

        head = insert(head, 80, 2);
        printList(head);
    }

    private static Node insert(Node head, int data, int pos) {
        Node temp = new Node(data);
        if (pos == 1) {
            temp.next = head;
            return temp;
        }

        // find previous node
        Node curr = head;
        for (int i = 0; i < pos - 2 && curr != null; i++) {
            curr = curr.next;
        }
        // pos > length of list
        if (curr == null) {
            return head;
        }
        temp.next = curr.next;
        curr.next = temp;
        return head;
    }
}

Why are we traversing till pos-2? Let us understand it through an example, we want to insert an element at 4th position. Initial we were at 1st position, and we have to reach at the 3rd position so that we can make 3rd_node.next = new_node.

  • Position 1: If pos is 1, the new node becomes the new head, so no traversal is needed.
  • Position pos: For any other position, you need to insert the new node after the pos-1 node.
  • Traversal pos-2: This means you need to stop at the node before the insertion point to properly link the new node in the list.

c. Delete in Single Linked List

1. Delete the First Node in Singly Linked List

Initial linked List: 10 => 20 => 30 => null
Delete First Node
Output: 20 => 30 => null

Initial linked List: 10 => null
Delete First Node
Output: null

Initial linked List: null
Delete First Node
Output: null

In main method:-

head = deleteFirst(head);
printList(head);

Method to delete the first node in Single Linked List

private static Node deleteFirst(Node head) {
    if (head == null) {
        return head;
    }
    return head.next;
}

Time complexity: O(1)

2. Delete the Last Node in Singly Linked List

If the size of list is 0 or 1 then after deleting the last node, head will be null. In other cases, same head is returned after deleting the last node.

private static Node deleteLast(Node head) {
    if (head == null || head.next == null) {
        return null;
    }

    // move to the second last node
    Node curr = head;
    while (curr.next.next != null) {
        curr = curr.next;
    }
    curr.next = null;
    return head;
}

Time complexity: O(n)

d. Search in Single Linked List

Given a linked list of n nodes and a key, the task is to check if the key is present in the linked list or not. Problem.

Linked List: 10 => 5 => 20 => 15 => null
Item to Search: 20
Index: 3

Linked List: 10 => 5 => null
Item to Search: 10
Index: 1

Linked List: 10 => 5 => 20 => 15 => null
Item to Search: 30
Index: -1

1. Iterative Approach to Search in a Linked List

private static int search(Node head, int x) {
    Node curr = head;
    for (int i = 1; curr != null; i++) {
        if (curr.data == x) {
            return i;
        }
        curr = curr.next;
    }
    return -1;
}

2. Recursive Approach to Search in a Linked List

private static int recursiveSearch(Node head, int x) {
    if (head == null) {
        return -1;
    }
    if (head.data == x) {
        return 1;
    }
    int res = recursiveSearch(head.next, x);
    if (res == -1) {
        return -1;
    }
    return res + 1;
}

Time complexity: O(n) in both iterative and recursive approaches. Auxilary space in iterative approach O(1) and auxilary space in recursive approach is O(n).

Linked List does not allow binary search to be implemented in O(log n), because we can’t find the middle node in O(1) time. However there are variations of linked list (skip list) which do some overhead and allow binary search in case of sorted list in O(log n).

Doubly Linked List

class Node {
    int data;
    Node prev; // null by default
    Node next; // null by default

    public Node(int data) {
        this.data = data;
    }
}
public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);

        // link head & temp1
        head.next = temp1;
        temp1.prev = head;

        // link temp1 & temp2
        temp1.next = temp2;
        temp2.prev = temp1;
    }
}

Problem

Advantages of Doubly Linked List over Singly Linked List

  • It can be traversed in both directions.
  • A given node can be deleted in O(1) time with a given reference/pointer in it.
  • We can insert/delete before a given node.
  • We can insert/delete from both ends in O(1) by maintaining the tail.

Disadvantages of Doubly Linked List over Singly Linked List

  • It takes extra space for the previous reference.
  • Code becomes more complex.

a. Insert in Doubly Linked List

1. Insert at the beginning of the Doubly Linked List

private static Node insertAtBegin(Node head, int x) {
    Node node = new Node(x);
    node.next = head;
    if (head != null) {
        head.prev = node;
    }
    return node;
}

2. Insert at the End of the Doubly Linked List

private static Node insertAtEnd(Node head, int x) {
    Node node = new Node(x);
    if (head == null) {
        return node;
    }
    Node curr = head;
    while (curr.next != null) {
        curr = curr.next;
    }
    curr.next = node;
    node.prev = curr;
    return head;
}

Problem: Insert at the given position in a Doubly linked list

b. Reverse in Doubly Linked List

Reverse a Doubly Linked List. Problem

Given list: 10 <=> 20 <=> 30 <=> 40
After Reverse: 40 <=> 30 <=> 20 <=> 10

Given list: 10
After Reverse: 10

Given list: null
After Reverse: null

We have to swap the references of the previous and next references.

private static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node prev = null, curr = head;
    while (curr != null) {
        // swap
        prev = curr.prev;
        curr.prev = curr.next;
        curr.next = prev;

        // move to next node
        // next has become previous
        curr = curr.prev;
    }
    return prev.prev;
}

c. Delete in Doubly Linked List

1. Delete the Head (First node) of a Doubly Linked List

Given list: 10 <=> 20 <=> 30 <=> 40
After deleting head: 20 <=> 30 <=> 40

Given list: 10
After deleting head: null

Given list: null
After deleting head: null

private static Node deleteHead(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    head = head.next;
    head.prev = null;
    return head;
}

2. Delete the last node of a Doubly Linked List

private static Node deleteLast(Node head) {
    if (head == null || head.next == null) {
        return null;
    }

    // Go to the last node
    Node curr = head;
    while (curr.next != null) {
        curr = curr.next;
    }

    // Remove the last node
    curr.prev.next = null;
    return head;
}

Time complexity: O(n). If we maintain the tail node then we don’t have to reach the last node therefore time complexity to delete the last node will be O(1) in that case. Problem: Delete a given node in Doubly linked list

Circular Linked List

In a circular linked list, the next of the last node is not null rather it points to the head (first node) of the linked list. A circular linked list can be either singly linked list or a doubly linked list. The structure of a circular linked list is the same as singly/double linked list. We will focus on the singly circular linked list.

class Node {
    int data;
    Node next; // null by default

    public Node(int data) {
        this.data = data;
    }
}
public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        Node temp3 = new Node(15);
        head.next = temp1;
        temp1.next = temp2;
        temp2.next = temp3;

        // Map last node with head
        temp3.next = head;
        printList(head);
    }

    private static void printList(Node head) {
        if (head == null) {
            return;
        }
        Node curr = head;
        do {
            System.out.print(curr.data + " ");
            curr = curr.next;
        } while (curr != head);
        System.out.println();
    }
}

In the circular linked list also, an empty list will have head = null;

Advantages of Circular Linked List

  • We can traverse the whole list from any node.
  • Implementation of algorithms like round robin.
  • We can insert at the beginning and end by just maintaining one tail reference/pointer.

Disadvantages of Circular Linked List

  • Implementations of operations become complex

a. Traversal in Circular Linked List

We have already traversal using the do-while loop. Let us see using a for loop.

private static void printList(Node head) {
    if (head == null) {
        return;
    }
    System.out.print(head.data + " ");

    // Start from the second node
    for (Node r = head.next; r != head; r = r.next) {
        System.out.print(r.data + " ");
    }
    System.out.println();
}

b. Insert in Circular Linked List

Insert at the beginning of the Circular Linked List

A naive solution is to traverse till the end of the last node and change its head.

private static Node insertAtBegin(Node head, int k) {
    Node node = new Node(k);
    if (head == null) {
        node.next = node;
    } else {
        // Go to last node
        Node curr = head;
        while (curr.next != head) {
            curr = curr.next;
        }
        curr.next = node;
        node.next = head;
    }

    return node;
}

Time complexity: O(n)

We can optimize it to O(1). One way to use tail pointer. Another way is to insert at 2nd position and swap 1st and 2nd position elements. Steps:-

  • Insert element at 2nd index.
  • Swap data from 1st and 2nd index.
private static Node insertAtBegin(Node head, int k) {
    Node temp = new Node(k);
    if (head == null) {
        temp.next = temp;
        return temp;
    }
    // Insert at 2nd position
    temp.next = head.next;
    head.next = temp;

    // Swap 1st and 2nd elements
    int t = head.data;
    head.data = temp.data;
    temp.data = t;

    return head; 
}

Insert at the End of the Circular Linked List
A naive solution is to find the last node and insert there.

private static Node insertAtEnd(Node head, int k) {
    Node temp = new Node(k);
    if (head == null) {
        temp.next = temp;
        return temp;
    }
    Node curr = head;
    while (curr.next != head) {
        curr = curr.next;
    }
    curr.next = temp;
    temp.next = head;
    return head;
}

Time complexity: O(n). We can optimize it to O(1). One way is to also maintain tail pointer. Another way is to insert at 2nd node, swap 1st and 2nd node elements, and mark 2nd position as head.

private static Node insertAtEnd(Node head, int k) {
    Node temp = new Node(k);
    if (head == null) {
        temp.next = temp;
        return temp;
    }
    // Insert at 2nd node
    temp.next = head.next;
    head.next = temp;

    // Swap 1st & 2nd node elements
    int t = temp.data;
    temp.data = head.data;
    head.data = t;

    // return second node as head
    return temp;
}

In main method, we always assign resultant as head:-

head = insertAtEnd(head, 80);
printList(head);

c. Delete in Circular Linked List

Delete Head of Circular Linked List

private static Node deleteAtBegin(Node head) {
    if (head == null || head.next == null) {
        return null;
    }

    // Replace 1st node data with 2nd node data
    head.data = head.next.data;

    // Unlink 2nd node
    head.next = head.next.next;

    return head;
}

Time complexity: O(1)

Delete Kth Node of a Circular Linked List
Assumption: Number of nodes >= k

The problem can be divided into 2 parts:- When k = 1 & When k > 1. For k == 1 case, we will use the previous deleteAtBegin() method.

private static Node deleteAtK(Node head, int pos) {
    if (head == null) {
        return null;
    }
    if (pos == 1) {
        return deleteAtBegin(head);
    }
    Node curr = head;
    for (int i = 0; i < pos - 2; i++) {
        curr = curr.next;
    }
    curr.next = curr.next.next;
    return head;
}

Circular Doubly Linked List

  • Every node will have two pointers/references: previous and next.
  • The previous of head is linked to last node.
  • The next of last node is linked to head.

Advantages of circular doubly linked list

  • We get all advantages of circular and doubly linked lists.
  • We can access last node in constant time without maintaining extra tail pointer/references.

In insertAtEnd() do everything same as insertAtBegin() but instead of returing temp, return the head.

class Node {
    int data;
    Node next; // null by default
    Node prev; // null by default

    public Node(int data) {
        this.data = data;
    }
}

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        Node temp3 = new Node(15);

        // map head with temp1
        head.next = temp1;
        temp1.prev = temp2;

        // map temp1 with temp2
        temp1.next = temp2;
        temp2.prev = temp1;

        // map temp2 with temp3
        temp2.next = temp3;
        temp3.prev = temp2;

        // make it circular
        head.prev = temp3;
        temp3.next = head;

        printList(head);

        head = insertAtBegin(head, 80);
        printList(head);

        head = insertAtEnd(head, 90);
        printList(head);
    }

    private static Node insertAtEnd(Node head, int k) {
        Node temp = new Node(k);
        if (head == null) {
            temp.next = temp;
            temp.prev = temp;
            return temp;
        }
        temp.prev = head.prev;
        temp.next = head;
        head.prev.next = temp;
        head.prev = temp;

        return head;
    }

    private static Node insertAtBegin(Node head, int k) {
        Node temp = new Node(k);
        if (head == null) {
            temp.next = temp;
            temp.prev = temp;
            return temp;
        }
        temp.prev = head.prev;
        temp.next = head;
        head.prev.next = temp;
        head.prev = temp;

        return temp;
    }

    private static void printList(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.data + " ");

        // start from second node
        for (Node r = head.next; r != head; r = r.next) {
            System.out.print(r.data + " ");
        }
        System.out.println();
    }
}

1. Insert in a Sorted Singly Linked List

A sorted linked list and an element is given. We have to insert the given element such that linked list should remain sorted.

Input: 10 => 20 => 30 => 40
x = 25
Output: 10 => 20 => 25 => 30 => 40

Input: 10 => 25
x = 5
Output: 5 => 10 => 25

Input: 10 => 25
x = 30
Output: 10 => 25 => 30

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node1 = new Node(20);
        Node node2 = new Node(30);
        Node node3 = new Node(40);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        printList(head);

        head = sortedInsert(head, 5);
        head = sortedInsert(head, 45);
        head = sortedInsert(head, 25);
        printList(head);

        head = sortedInsert(null, 5);
        printList(head);
    }

    private static Node sortedInsert(Node head, int item) {
        Node node = new Node(item);
        if (head == null) {
            return node;
        } else if (item < head.data) {
            node.next = head;
            return node;
        }
        Node curr = head;
        while (curr.next != null && curr.next.data < item) {
            curr = curr.next;
        }
        node.next = curr.next;
        curr.next = node;
        return head;
    }

    private static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }
}

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }
}

2. Find the Middle of LinkedList

If the length of the list is odd then display the middle node element but if the length of the list is even then there will be two middle nodes so display the second middle node element. Problem: 876

Input: 10 => 5 => 20 => 15 => 25
Middle Element: 20

Input: 10 => 5 => 20 => 15 => 25 => 30
Middle Element: 15

Input: 10
Middle Element: 10

Input: 10 => 20
Middle Element: 20

Input: Null
Middle Element: N/A

The naive solution is to count the number of nodes and then traverse to the middle of the count to get the middle element. But it requires two traversal. How it can be done in a single traversal?

We can do that using slow and fast references. The slow and fast references will move one & two nodes respectively in each iteration. So when the fast reference reaches the end of the linked list, the slow reference will be in the middle.

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node1 = new Node(20);
        Node node2 = new Node(30);
        Node node3 = new Node(40);
        Node node4 = new Node(50);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        printList(head);

        displayMiddleElement(head);
    }

    private static void displayMiddleElement(Node head) {
        if (head == null) {
            return;
        }
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(slow.data);
    }
}

3. Find n-th Node From End of Linked List

Input: 10 => 5 => 20 => 15 => 25
N = 2
Element: 15

Input: 10 => 5 => 20
N = 3
Element: 10

Input: 10 => 15
N = 3
Element: N/A

Input: 10 => 20 => 30 => 40
N = 1
Element: 40

Method-1: Using length of Linked List
We have to display the (len – N + 1)th element.

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node1 = new Node(20);
        Node node2 = new Node(30);
        Node node3 = new Node(40);
        Node node4 = new Node(50);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        printList(head);

        nthNodeFromEnd(head, 2);
    }

    private static void nthNodeFromEnd(Node head, int n) {
        if (head == null) {
            return;
        }
        int len = 0;
        for (Node curr = head; curr != null; curr = curr.next) {
            len++;
        }
        if (n > len) {
            return;
        }
        Node curr = head;
        for (int i = 1; i < len - n + 1; i++) {
            curr = curr.next;
        }
        System.out.println(curr.data);

    }
}

Method 2: Using Two Pointer/References

This method does not find the length of the linked list. It uses two references:- first and second.

  • Move first reference N positions ahead
  • Start second reference from head
  • Now move both first and second references with same speed. The time when first reaches the end, the second will at the required position.
private static void nthNodeFromEnd(Node head, int n) {
    if (head == null) {
        return;
    }

    Node first = head;
    for (int i = 1; i <= n; i++) {
        if (first == null) return; // Ensures N is not > length 
        first = first.next;
    }

    Node second = head;
    while (first != null) {
        first = first.next;
        second = second.next;
    }

    System.out.println(second.data);
}

a. Delete n-th Node From End of Linked List

Given the head of a linked list, remove the nth node from the end of the list and return its head. Problem: 19

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

        // Move fast pointer n + 1 steps ahead
        for (int i = 1; i <= n + 1; i++) {
            fast = fast.next;
        }

        // Move both fast and slow pointers until fast reaches the end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove the nth node from the end
        slow.next = slow.next.next;

        // Return the head of the modified list
        return dummy.next;
    }
}

b. Delete the Middle Node of a Linked List

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list. Problem: 2095

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

4. Reverse a linked list

Input: 10 => 20 => 30 => 40
Reverse: 40 => 30 => 20 => 10
Problem: 206

Input: 10
Reverse: 10

Input: null
Reverse: null

The naive solution is to copy linked list to an ArrayList and then place elements into the linked list in reverse order.

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

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node1 = new Node(20);
        Node node2 = new Node(30);
        Node node3 = new Node(40);
        Node node4 = new Node(50);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        printList(head);

        head = reverse(head);
        printList(head);
    }

    private static Node reverse(Node head) {
        List<Integer> arr = new ArrayList<>();
        for (Node curr = head; curr != null; curr = curr.next) {
            arr.add(curr.data);
        }
        for (Node curr = head; curr != null; curr = curr.next) {
            curr.data = arr.remove(arr.size() - 1);
        }
        return head;
    }
}

Output:-
10 20 30 40 50
50 40 30 20 10

Time complexity: O(n), and space complexity: O(n). It requires two traversal.

The efficient solution is to change the link instead of changing the data.

private static Node reverse(Node head) {
    Node prev = null;
    Node curr = head;
    while (curr != null) {
        Node next = curr.next;  // Store next node
        curr.next = prev;       // Reverse current node's pointer
        prev = curr;            // Move pointers one position ahead
        curr = next;
    }
    return prev; // prev is the new head of the reversed list
}

Time complexity: O(n), and space complexity: O(1).

Recursive Approach-1

private static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node rest_head = reverse(head.next);
    Node rest_tail = head.next;
    rest_tail.next = head;
    head.next = null;
    return rest_head;
}

Recursive Approach-2

private static Node reverse(Node current, Node prev) {
    if (current == null) {
        return prev;
    }
    Node next = current.next;
    current.next = prev;
    return reverse(next, current);
}

5. Remove Duplicates from a Sorted Linked List

Input: 10 => 20 => 20 => 30 => 30 => 30
Output: 10 => 20 => 30

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node1 = new Node(20);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(30);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        printList(head);

        removeDuplicate(head);
        printList(head);
    }

    private static void removeDuplicate(Node head) {
        Node curr = head;
        while (curr != null && curr.next != null) {
            if (curr.data == curr.next.data) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
    }
}

6. Reverse a Linked List in Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. Problem: 25

Input: 10 => 20 => 30 => 40 => 50 => 60
K = 3
Output: 30 => 20 => 10 => 60 => 50 => 40

Input: 10 => 20 => 30 => 40 => 50
K = 3
Output: 30 => 20 => 10 => 50 => 40

Input: 10 => 20 => 30
K = 4
Output: 30 => 20 => 10

Recursive Solution

public class Test {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node node1 = new Node(20);
        Node node2 = new Node(30);
        Node node3 = new Node(40);
        Node node4 = new Node(50);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        printList(head);

        head = reverseKGroup(head, 3);
        printList(head);
    }

    private static Node reverseKGroup(Node head, int k) {
        Node curr = head, prev = null, next = null;
        int count = 0;
        while (curr != null && count < k) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            count++;
        }
        if (next != null) {
            Node rest_head = reverseKGroup(next, k);
            head.next = rest_head;
        }
        return prev;
    }
}

Iterative Solution

  1. Initialize: Set curr to head, prevFirst to null, and isFirstPass to true.
  2. Reverse Groups:
  • For each group of size k:
    • Reverse k nodes.
    • Connect the previous group to the current group.
  1. Update:
  • Update head on the first pass.
  • Set prevFirst to the last node of the current group.
  1. Return: Return the new head of the list.
private static Node reverseKGroup(Node head, int k) {
    // Initialize current node and previous group's last node
    Node curr = head, prevFirst = null; 
    // To check if we are on the first group of k nodes
    boolean isFirstPass = true; 

    while (curr != null) {
        // `first` is the starting node of the current group, `prev` for reversing
        Node first = curr, prev = null; 
        int count = 0;

        // Reverse k nodes
        while (curr != null && count < k) {
            Node next = curr.next; // Save next node
            curr.next = prev; // Reverse current node's pointer
            prev = curr; // Move `prev` to current node
            curr = next; // Move `curr` to next node
            count++;
        }

        // If it's the first group, update the head of the list
        if (isFirstPass) {
            head = prev;
            isFirstPass = false;
        } else {
            // Connect the previous group's last node to the current group's first node
            prevFirst.next = prev;
        }

        // Update `prevFirst` to the last node of the current group
        prevFirst = first;
    }

    return head; // Return the new head of the list
}

Modified version:- If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head, prevFirst = null;
        boolean isFirstPass = true;

        while (curr != null) {
            ListNode first = curr, prev = null;
            int count = 0, len = 0;

            // Check if there are enough nodes left to reverse
            for (ListNode i = curr; i != null && len < k; i = i.next) {
                len++;
            }

            // If there are not enough nodes left, don't reverse and return the head
            if (len < k) {
                if (prevFirst != null) {
                    prevFirst.next = curr;
                }
                break;
            }

            // Reverse the nodes in groups of k
            while (curr != null && count < k) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
                count++;
            }

            if (isFirstPass) {
                head = prev;
                isFirstPass = false;
            } else {
                prevFirst.next = prev;
            }

            prevFirst = first;
        }

        return head;
    }
}

7. Detect loop in a Linked List

Problem: 141

import java.util.HashSet;
import java.util.Set;

public class Test {
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        ListNode node1 = new ListNode(20);
        ListNode node2 = new ListNode(40);
        ListNode node3 = new ListNode(70);
        ListNode node4 = new ListNode(80);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // loop

        System.out.println(containsLoop(head));
    }

    private static boolean containsLoop(ListNode head) {
        // TODO
    }
}

Method-1: Using Set

Store each node to HashSet and check whether node already present in the set or not.

private static boolean containsLoop(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    for (ListNode curr = head; curr != null; curr = curr.next) {
        if (set.contains(curr)) {
            return true;
        }
        set.add(curr);
    }
    return false;
}

Time complexity O(n), auxiliary space O(n).

Method 2: Floyd’s Cycle Detection

  1. Initialize slow and fast variable pointing to the head.
  2. Move slow variable by one node and fast variable by two node. If they meet then there is a loop else fast will end up reaching null.
private static boolean containsLoop(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Points to Note:-

  • Fast will enter into the loop before (or at the same as slow).
  • Let fast be k distance ahead of slow when slow enters the loop where K >= 0.
  • This distance keeps on increasing by one in every movement of both pointers.
  • When distance becomes length of cycle, they must meet.

Time complexity: O(m + n) where n is length of the loop and m is the length of remaining linked list.

a. Detect and Remove loop in a Linked List

If the linked list contains the loop then break that loop (unlink them).

To solve this we can use the Floyd’s algorithm to detect the loop. Steps:-

  • If slow and fast do not meet, there’s no loop, and the function returns.
  • If they meet, move slow to the head and keep fast at the meeting point.
  • Move both pointers one step at a time until slow.next equals fast.next. This points to the start of the loop.
  • Set fast.next to null to break the loop.
public class Test {
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        ListNode node1 = new ListNode(20);
        ListNode node2 = new ListNode(40);
        ListNode node3 = new ListNode(70);
        ListNode node4 = new ListNode(80);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;

        breakLoop(head);
        printList(head);
    }

    private static void breakLoop(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (slow != fast) {
            return;
        }
        slow = head;
        // check slow.next & fast.next but not the slow & fast
        while (slow.next != fast.next) {
            slow = slow.next;
            fast = fast.next;
        }
        fast.next = null;
    }
}
  • In case of linked list contains a loop then (m + k) is always a multiple of n.
  • If (m + k) is a multiple of n, then the second meeting point is going to be the first node of the loop.

b. Find the Length of Loop

To find the length of the loop, once we find that there is a loop then we keep one pointer fixed and keep moving another pointer by one node and keep incrementing the count variable till both pointer meet. Problem

private static int lengthOfLoop(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }
    int count = 0;
    if (slow == fast) {
        do {
            count++;
            slow = slow.next;
        } while (slow != fast);
    }
    return count;
}

c. Find the first node of the loop

To remove the loop, we found the first node and then we removed the loop. Problem: 142

public class Test {
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        ListNode node1 = new ListNode(20);
        ListNode node2 = new ListNode(40);
        ListNode node3 = new ListNode(70);
        ListNode node4 = new ListNode(80);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // Creating a loop

        ListNode ln = firstNode(head);
        if (ln != null) {
            System.out.println(ln.data);
        }
    }

    private static ListNode firstNode(ListNode head) {
        if (head == null || head.next == null) { 
            return null; 
        }

        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (slow != fast) {
            return null; // No loop
        }
        slow = head;
        while (slow != fast) { 
            slow = slow.next;
            fast = fast.next;
        }
        return slow; // The start of the loop
    }
}

8. Delete a node with only a pointer given to it

You are given address or reference of a random node of a linked list, you have to delete this node. Problem: 237. Delete a Given Node. Points to consider:-

  • You will not be given access to the first node of head.
  • It is guaranteed that the given node node is not the last node in the linked list.
class Solution {
    public void deleteNode(ListNode node) {
        // It is not the last node
        // copy the data of next node
        node.val = node.next.val;
        // unlink the next node
        node.next = node.next.next;
    }
}

9. Segregate Even and Odd Nodes of a Linked List

All even values should appear first then odd values. The relative order of all odd values should be the same and the relative order of all even values should be the same. It is one of the popular interview questions by doing it through single traversal. Similar Problem: 328

Input: 17 => 15 => 8 => 12 => 10 => 5 => 4
Output: 8 => 12 => 10 => 4 => 17 => 15 => 5

Input: 8 => 12 => 10
Output: 8 => 12 => 10

Input: 1 => 3 => 5
Output: 1 => 3 => 5

A naive solution is to move one pointer to the end of the linked list, and again traverse from the start through another problem. If there is an odd element, then move them in the end. But it requires 2 traversal. We can do it in a single traversal as follows:-

  1. Initialize Pointers: eS, eE for the even list, oS, oE for the odd list, all to null.
  2. Traverse the List:
  • Iterate through the linked list.
  • For each node:
    • If even, add to the even list.
    • If odd, add to the odd list.
  1. Merge Lists:
  • Connect the even list to the odd list.
  • If one list is empty, return the original head.
  1. Return New Head: Return the head of the even list.
public class Test {
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        ListNode node1 = new ListNode(15);
        ListNode node2 = new ListNode(20);
        ListNode node3 = new ListNode(25);
        ListNode node4 = new ListNode(30);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        head = segregate(head);
        printList(head);
    }

    private static ListNode segregate(ListNode head) {
        ListNode eS, eE, oS, oE;
        eS = eE = oS = oE = null;
        for (ListNode curr = head; curr != null; curr = curr.next) {
            int x = curr.data;
            if (x % 2 == 0) {
                if (eS == null) {
                    eS = curr;
                    eE = eS;
                } else {
                    eE.next = curr;
                    eE = eE.next;
                }
            } else {
                if (oS == null) {
                    oS = curr;
                    oE = oS;
                } else {
                    oE.next = curr;
                    oE = oE.next;
                }
            }
        }
        if (oS == null || eS == null) {
            return head;
        }
        eE.next = oS;
        oE.next = null;
        return eS;
    }
}

10. Intersection Point of Two Linked Lists

Finding the intersection point of two linked lists means identifying the node where the two lists converge. In the below example, the intersection point is 40. Problem: 160

List 1: 10 -> 20 -> 30 \
                       -> 40 -> 50
List 2:        5 -> 15 /
public class Test {
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        // Creating the first linked list
        ListNode head1 = new ListNode(10);
        ListNode node1 = new ListNode(20);
        ListNode node2 = new ListNode(30);
        ListNode node3 = new ListNode(40);
        ListNode node4 = new ListNode(50);
        head1.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        // Creating the second linked list
        ListNode head2 = new ListNode(5);
        ListNode node5 = new ListNode(15);
        head2.next = node5;
        node5.next = node3; // Intersection point

        ListNode intersection = getIntersectionNode(head1, head2);
        if (intersection != null) {
            System.out.println("Intersection point data: " + intersection.data);
        } else {
            System.out.println("No intersection point");
        }
    }

    private static ListNode getIntersectionNode(ListNode head1, ListNode head2) {
        // TODO
        return null;
    }
}

Method-1: Using Set

  1. Create an empty HashSet.
  2. Traverse the first list and put all of its nodes into the HashSet.
  3. Traverse the second list and look for every node in HashSet. As soon as we find a node in the HashSet, we return the node.
private static ListNode getIntersectionNode(ListNode head1, ListNode head2) {
    Set<ListNode> set = new HashSet<>();
    for (ListNode curr = head1; curr != null; curr = curr.next) {
        set.add(curr);
    }
    for (ListNode curr = head2; curr != null; curr = curr.next) {
        if (set.contains(curr)) {
            return curr;
        }
        set.add(curr);
    }
    return null;
}

Time complexity: O(m + n), and auxiliary space: O(m)

Method-2

  1. Count nodes in both lists. Let counts be c1 and c2.
  2. Traverse the bigger list abs(c1 – c2) times.
  3. Traverse both lists simultaneously until we see a common node.
private static ListNode getIntersectionNode(ListNode head1, ListNode head2) {
    int c1 = 0, c2 = 0;

    // Count the length of the first linked list
    for (ListNode curr = head1; curr != null; curr = curr.next) {
        c1++;
    }

    // Count the length of the second linked list
    for (ListNode curr = head2; curr != null; curr = curr.next) {
        c2++;
    }

    // Calculate the difference in lengths
    int diff = Math.abs(c1 - c2);

    // Advance the pointer of the longer list by the difference in lengths
    ListNode curr1 = head1;
    while (diff > 0) {
        diff--;
        curr1 = curr1.next;
    }

    ListNode curr2 = head2;

    // Move both pointers until they meet
    while (curr1 != null && curr2 != null) {
        if (curr1 == curr2) {
            return curr1; // Intersection point
        }
        curr1 = curr1.next;
        curr2 = curr2.next;
    }

    return null; // No intersection
}

11. Pairwise Swap Nodes of a Linked List

Input: 1=>2=>3=>4=>5=>6
Output: 2=>1=>4=>3=>6=>5

Input: 1=>2=>3=>4=>5
Output: 2=>1=>4=>3=>5

If there are odd nodes, keep swapping them and leave the last node as it is.

public class Test {
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        ListNode node1 = new ListNode(20);
        ListNode node2 = new ListNode(30);
        ListNode node3 = new ListNode(40);
        ListNode node4 = new ListNode(50);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        printList(head);
        pairWiseSwap(head);
        printList(head);
    }

    private static void pairWiseSwap(ListNode head) {
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            int t = curr.data;
            curr.data = curr.next.data;
            curr.next.data = t;
            curr = curr.next.next;
        }
    }
}

The time complexity is O(n) however since this linked list contains an int value therefore swapping was easy, but if it contains a large object then swapping might be costly. So, we should see an approach that does not swap the data rather it should change the link only.

private static ListNode pairWiseSwap(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode curr = head.next.next; // third node in the list
    ListNode prev = head; // first node in the list
    head = head.next; // New head of the list (second node)
    head.next = prev; // Swap the first two nodes

    while (curr != null && curr.next != null) {
        prev.next = curr.next; // Point the previous node to the second node of the current pair
        prev = curr; // Update the previous node to the current node
        ListNode next = curr.next.next; // Save the pointer to the next pair of nodes
        curr.next.next = curr; // Swap the current pair of nodes
        curr = next; // Move to the next pair of nodes
    }

    // Point the last node of the previous pair to the remaining nodes, if any
    prev.next = curr;

    // Return the new head of the list
    return head;
}

12. Clone a Linked List with Random References

    +---+---+       +---+---+       +---+---+
    | 1 | o-+------>| 2 | o-+------>| 3 | o-|
    +---+---+       +---+---+       +---+---+
      |               |               |
      +---------------+               |
      |                               |
      +-------------------------------+

Cloning a linked list with random references is an interesting problem. It involves creating a deep copy of a linked list where each node has two pointers: one to the next node and another to a random node in the list.

class Node {
    int data;
    Node next, random;

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.random = null;
    }
}

public class Test {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        head.next = node2;
        node2.next = node3;

        head.random = node3;
        node2.random = head;
        node3.random = node2;

        Node clonedList = cloneList(head);
        printList(clonedList);
    }

    private static Node cloneList(Node head) {
        // TODO
    }

    private static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print("Node data: " + curr.data);
            if (curr.random != null) {
                System.out.print(", Random data: " + curr.random.data);
            }
            System.out.println();
            curr = curr.next;
        }
    }
}

Using HashMap

private static Node cloneList(Node head) {
    if (head == null) {
        return null;
    }

    // Step 1: Create a mapping from original nodes to their copies
    Map<Node, Node> map = new HashMap<>();
    for (Node curr = head; curr != null; curr = curr.next) {
        map.put(curr, new Node(curr.data));
    }

    // Step 2: Set the next and random pointers for the copied nodes
    for (Node curr = head; curr != null; curr = curr.next) {
        Node clonedNode = map.get(curr);
        clonedNode.next = map.get(curr.next);
        clonedNode.random = map.get(curr.random);
    }

    // Return the head of the cloned list
    return map.get(head);
}

Without using HashMap

private static Node cloneList(Node head) {
    if (head == null) {
        return null;
    }

    // Step 1: Create copies of each node
    Node curr = head;
    while (curr != null) {
        Node newNode = new Node(curr.data);
        newNode.next = curr.next;
        curr.next = newNode;
        curr = newNode.next;
    }

    // Step 2: Set the random pointers
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }

    // Step 3: Restore the original list and separate the clone
    curr = head;
    Node cloneHead = head.next;
    Node cloneCurr = cloneHead;
    while (curr != null) {
        curr.next = curr.next.next;
        if (cloneCurr.next != null) {
            cloneCurr.next = cloneCurr.next.next;
        }
        curr = curr.next;
        cloneCurr = cloneCurr.next;
    }

    return cloneHead;
}

13. LRU (Least Recently Used) Cache Design

The LRU (Least Recently Used) Cache is a popular and practical caching algorithm used in systems to manage memory efficiently. The LRU Cache evicts the least recently used items first when the cache reaches its capacity. This approach ensures that frequently accessed items remain available while older, less accessed items are replaced.

Design Requirements:-

  1. Capacity: Define a maximum capacity for the cache. Once the cache reaches this capacity, the least recently used item will be removed to make space for new items.
  2. Operations:
  • get(key): Retrieve the value associated with the key if it exists in the cache. If the key is not found, return -1.
  • put(key, value): Insert or update the value associated with the key. If the cache is at capacity, remove the least recently used item before inserting the new item.
  1. Performance: Both get and put operations should be performed in O(1) time complexity.

If the item is already present in the cache then it is called a hit, else it is called a miss.

The naive solution is to use an array. But the time complexity will be O(n) in both cache hit and cache miss cases because we have to traverse the complete array.

We can notice that we need a data structure that can quickly tell us whether the element is present in the cache or not. Hashtable can do it in O(1). However, hashing is unordered and they don’t preserve the order. To preserve the order we can use a double linked list with hashing.

To achieve O(1) time complexity for both get and put operations, a combination of a doubly linked list and a hash map can be used:

  • Doubly Linked List: Maintains the order of the items based on their usage. The most recently used items are moved to the head of the list, and the least recently used items are at the tail.
  • Hash Map: Provides O(1) access to the items in the cache by mapping keys to their corresponding nodes in the doubly linked list.

Implementation algorithm:-

lru(x) {
    // look for x in HashTable

    // a. If found (Hit), find the reference of the node in DLL.
    //    And move the node to the front of DLL.

    // b. If not found (miss)
        // 1. Insert a new node at the front of the DLL
        // 2. Insert an entry into the HashTable
}

Time complexity:- Hit: O(1), Miss: O(1).

Example Implementation in Java:

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    class Node {
        int key, value;
        Node prev, next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);
        insert(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        } else if (map.size() == capacity) {
            remove(tail.prev);
        }
        insert(new Node(key, value));
    }

    private void remove(Node node) {
        map.remove(node.key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insert(Node node) {
        map.put(node.key, node);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Here’s an example class to demonstrate the use of the LRU Cache we’ve implemented. We’ll create an instance of the LRUCache and perform some get and put operations to see how the cache behaves.

Example Usage:

public class TestLRUCache {
    public static void main(String[] args) {
        // Create an LRUCache with capacity 2
        LRUCache cache = new LRUCache(2);

        // Perform some put operations
        cache.put(1, 1); // Cache is {1=1}
        cache.put(2, 2); // Cache is {1=1, 2=2}

        // Perform a get operation
        System.out.println(cache.get(1)); // Returns 1, Cache is {2=2, 1=1}

        // Perform another put operation
        cache.put(3, 3); // LRU key was 2, evicts key 2, Cache is {1=1, 3=3}

        // Try to get a value that was evicted
        System.out.println(cache.get(2)); // Returns -1 (not found)

        // Perform another put operation
        cache.put(4, 4); // LRU key was 1, evicts key 1, Cache is {3=3, 4=4}

        // Check some values
        System.out.println(cache.get(1)); // Returns -1 (not found)
        System.out.println(cache.get(3)); // Returns 3, Cache is {4=4, 3=3}
        System.out.println(cache.get(4)); // Returns 4, Cache is {3=3, 4=4}
    }
}
  1. Create an LRUCache Instance: Initialize the LRU Cache with a capacity of 2.
  2. Perform Operations:
  • put(1, 1): Adds (1, 1) to the cache.
  • put(2, 2): Adds (2, 2) to the cache.
  • get(1): Returns the value associated with key 1 and moves key 1 to the front (most recently used).
  • put(3, 3): Adds (3, 3) to the cache, evicts key 2 since it’s the least recently used.
  • get(2): Returns -1 since key 2 was evicted.
  • put(4, 4): Adds (4, 4) to the cache, evicts key 1.
  • get(1): Returns -1 since key 1 was evicted.
  • get(3): Returns the value associated with key 3.
  • get(4): Returns the value associated with key 4.

By following these steps, you can see how the LRU Cache maintains its capacity while ensuring the most recently used items are retained, and the least recently used items are evicted when necessary.

14. Merge Two Sorted LinkedList

Merge two sorted linked lists and the resultant linked list should be sorted. Problem: 21

public class Test {
    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        Node head1 = new Node(10);
        Node node1 = new Node(15);
        Node node2 = new Node(25);
        head1.next = node1;
        node1.next = node2;

        Node head2 = new Node(9);
        Node nodeB1 = new Node(18);
        Node nodeB2 = new Node(20);
        Node nodeB3 = new Node(27);
        head2.next = nodeB1;
        nodeB1.next = nodeB2;
        nodeB2.next = nodeB3;

        System.out.println("List 1:");
        printList(head1);
        System.out.println("List 2:");
        printList(head2);

        Node mergedHead = merge(head1, head2);
        System.out.println("Merged List:");
        printList(mergedHead);
    }

    private static Node merge(Node head1, Node head2) {
        // Corner cases
        if (head1 == null) {
            return head2;
        } else if (head2 == null) {
            return head1;
        }

        // Initialize the head of the merged list
        Node head;
        if (head1.data < head2.data) {
            head = head1;
            head1 = head1.next;
        } else {
            head = head2;
            head2 = head2.next;
        }

        Node curr = head;

        // Merge the lists
        while (head1 != null && head2 != null) {
            if (head1.data < head2.data) {
                curr.next = head1;
                head1 = head1.next;
            } else {
                curr.next = head2;
                head2 = head2.next;
            }
            curr = curr.next;
        }

        // Attach the remaining nodes
        if (head1 != null) {
            curr.next = head1;
        } else {
            curr.next = head2;
        }

        return head;
    }

    private static void printList(Node head) {
        for (Node curr = head; curr != null; curr = curr.next) {
            System.out.print(curr.data + " ");
        }
        System.out.println();
    }
}

Time complexity O(m + n) where m and n are the length of the lists, auxiliary space O(1).

15. Palindrome Linked List

Check whether the given linked list is palindrome or not. Problem: 234

Input: R => A => D => A => R
Output: Yes

Input: P => R => O => G => R => A => M
Output: No

public class Test {
    static class Node {
        char data;
        Node next;

        public Node(char data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        Node list1 = arrayToList("RADAR".toCharArray());
        Node list2 = arrayToList("program".toCharArray());
        printList(list1);
        printList(list2);
        System.out.println(isPalindrome(list1));
        System.out.println(isPalindrome(list2));
    }

    private static boolean isPalindrome(Node list) {
        // TODO
    }

    private static Node arrayToList(char[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        Node node = new Node(arr[0]);
        Node head = node, curr = head;
        for (int i = 1; i < arr.length; i++) {
            curr.next = new Node(arr[i]);
            curr = curr.next;
        }
        return head;
    }

    private static void printList(Node head) {
        for (Node curr = head; curr != null; curr = curr.next) {
            System.out.print(curr.data + " ");
        }
        System.out.println();
    }
}

A naive solution is to use the stack data structure. Put all the values from the linked list into the stack. Now remove items from the stack and traverse the linked list from the beginning. Compare both popped items and linked list elements.

private static boolean isPalindrome(Node list) {
    Deque<Character> stack = new ArrayDeque<>();

    // Push all nodes data onto the stack
    for (Node curr = list; curr != null; curr = curr.next) {
        stack.push(curr.data);
    }

    // Pop from the stack and compare with nodes data
    for (Node curr = list; curr != null; curr = curr.next) {
        if (stack.pop() != curr.data) {
            return false;
        }
    }

    return true;
}

Time complexity and auxiliary space O(n).

Let us see how it can be done in O(1) auxiliary space. The idea is to reverse the list from mid to end and then compare from beginning and mid elements.

private static boolean isPalindrome(Node list) {
    Node fast = list, slow = list;

    // Move slow to the middle and fast to the end of the list
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse the second half of the list
    Node rev = reverse(slow, null);
    Node curr = list;

    // Compare the first half with the reversed second half
    while (rev != null) {
        if (curr.data != rev.data) {
            return false;
        }
        rev = rev.next;
        curr = curr.next;
    }

    return true;
}

private static Node reverse(Node curr, Node prev) {
    if (curr == null) {
        return prev;
    }
    Node next = curr.next;
    curr.next = prev;
    return reverse(next, curr);
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *