Linked List

Q: Reverse a linked list (iterative and recursive)

Reverse a linked list (iterative and recursive) - A Easy difficulty question commonly asked at Amazon. Study Linked List patterns and Java implementation to solve this.

Q: Detect cycle and find the starting node of the cycle

Detect cycle and find the starting node of the cycle - A Medium difficulty question commonly asked at Google. Study Linked List patterns and Java implementation to solve this.

Q: Find the nth node from the end in one pass

Find the nth node from the end in one pass - A Easy difficulty question commonly asked at Microsoft. Study Linked List patterns and Java implementation to solve this.

Q: Check if a linked list is a palindrome

Check if a linked list is a palindrome - A Medium difficulty question commonly asked at Facebook. Study Linked List patterns and Java implementation to solve this.

Q: Flatten a multilevel doubly linked list

Flatten a multilevel doubly linked list - A Medium difficulty question commonly asked at Atlassian. Study Linked List patterns and Java implementation to solve this.

Beginner

Master pointer manipulation, cycle detection, and reversal — interview favorites at every top company.

Think of it this way

Think of a treasure hunt where each clue tells you exactly where the next clue is hidden. You cannot jump to clue 5 directly — you must follow the chain from clue 1. The upside? Hiding a new clue anywhere is easy: just change what the previous clue points to. No shuffling required, unlike an array.

In code, it looks like thisJava

class Node {
    int data;
    Node next;           // pointer to the next clue
    Node(int data) { this.data = data; }
}

Node head = new Node(1);
head.next       = new Node(2);  // 1 → 2 → null
head.next.next  = new Node(3);  // 1 → 2 → 3 → null
// To reach node 3 you MUST start at head and follow .next twice

Overview

A linked list is a linear data structure where each element (node) contains data and a pointer to the next node. Unlike arrays, nodes are not stored in contiguous memory, so there is no random access. The key skill interviewers test is your ability to manipulate pointers cleanly without losing references. Java's LinkedList class is a doubly linked list, but interviews focus on singly linked lists implemented from scratch.

Time & Space Complexity

Operation	Time	Space
Access by index	`O(n)`	`O(1)`
Insert at head	`O(1)`	`O(1)`
Insert at tail	`O(n)`	`O(1)`
Delete at head	`O(1)`	`O(1)`
Delete by value	`O(n)`	`O(1)`
Search	`O(n)`	`O(1)`

Java Implementation

Java

public class LinkedList {

    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }

    // Reverse a linked list in-place — O(n)
    public static Node reverse(Node head) {
        Node prev = null;
        Node current = head;
        while (current != null) {
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    // Detect cycle using Floyd's algorithm — O(n), O(1) space
    public static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    // Find the middle node — O(n)
    public static Node findMiddle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Merge two sorted linked lists — O(n + m)
    public static Node mergeSorted(Node l1, Node l2) {
        Node dummy = new Node(0);
        Node current = dummy;
        while (l1 != null && l2 != null) {
            if (l1.data <= l2.data) { current.next = l1; l1 = l1.next; }
            else { current.next = l2; l2 = l2.next; }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

Key Points to Remember

Floyd's cycle detection (slow/fast pointer) detects cycles in O(n) with O(1) space
```
slow = slow.next;
fast = fast.next.next;
if (slow == fast) // cycle detected!
```
Always handle the null/head edge cases first — they cause most bugs
```
if (head == null || head.next == null) return head; // guard early
```

Reversing a linked list in-place uses three pointers: prev, current, next

Node prev = null, curr = head;
while (curr != null) {
    Node next = curr.next; // save next before overwriting
    curr.next = prev;      // reverse the pointer
    prev = curr;  curr = next;
}
// prev is now the new head

Use a dummy head node to simplify insertion/deletion at the head

Node dummy = new Node(0);
dummy.next = head; // operations on dummy.next avoid null checks

Finding the middle: slow pointer moves 1 step, fast pointer moves 2 steps

while (fast != null && fast.next != null) {
    slow = slow.next;        // 1 step
    fast = fast.next.next;   // 2 steps
}
// slow is now at the middle

Interview Questions

Reverse a linked list (iterative and recursive)

EasyAmazonSolve it

Detect cycle and find the starting node of the cycle

MediumGoogleSolve it

Find the nth node from the end in one pass

EasyMicrosoftSolve it

Check if a linked list is a palindrome

MediumFacebookSolve it

Flatten a multilevel doubly linked list

MediumAtlassianSolve it

Ask Aria about Linked List

Your personal AI tutor — ask anything about this concept

Arrays

Stack