Linked List for Software Engineering Job Interviews

(With Python, Java, C++, and JavaScript Code)

A Linked List is a linear data structure where elements are stored in nodes, and each node contains:

1. Data

2. Pointer/reference to the next node

Unlike arrays, linked lists are not stored contiguously in memory.

Companies like Google, Meta, Amazon, and Microsoft frequently ask linked list problems because they test:

• Pointer manipulation

• Problem-solving

• Memory understanding

• Edge case handling

• Time/space optimization

---

1. Types of Linked Lists

---

A. Singly Linked List

1 -> 2 -> 3 -> NULL

Each node points only to the next node.

---

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

---

Java

class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
        this.next = null;
    }
}

---

C++

class Node {
public:
    int val;
    Node* next;

    Node(int v) {
        val = v;
        next = NULL;
    }
};

---

JavaScript

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

---

B. Doubly Linked List

NULL <- 1 <-> 2 <-> 3 -> NULL

Each node contains:

• prev pointer

• next pointer

Used in:

• Browser history

• LRU Cache

• Undo/Redo

---

C. Circular Linked List

1 -> 2 -> 3
^         |
|_________|

Last node points back to the head.

---

2. Linked List vs Array

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Access	O(1)	O(n)
Insert at Head	O(n)	O(1)
Delete	O(n)	O(1) if pointer known
Dynamic Size	Difficult	Easy

---

3. Basic Operations

---

A. Traversal

---

Python

def print_list(head):
    curr = head

    while curr:
        print(curr.val, end=" ")
        curr = curr.next

---

Java

void printList(Node head) {
    Node curr = head;

    while (curr != null) {
        System.out.print(curr.val + " ");
        curr = curr.next;
    }
}

---

C++

void printList(Node* head) {
    Node* curr = head;

    while(curr != NULL) {
        cout << curr->val << " ";
        curr = curr->next;
    }
}

---

JavaScript

function printList(head) {
    let curr = head;

    while (curr) {
        console.log(curr.val);
        curr = curr.next;
    }
}

---

Complexity

Operation	Time	Space
Traversal	O(n)	O(1)

---

B. Insert at Beginning

---

Python

def insert_head(head, val):
    node = Node(val)
    node.next = head
    return node

---

Java

Node insertHead(Node head, int val) {
    Node node = new Node(val);
    node.next = head;
    return node;
}

---

C++

Node* insertHead(Node* head, int val) {
    Node* node = new Node(val);
    node->next = head;
    return node;
}

---

JavaScript

function insertHead(head, val) {
    let node = new Node(val);
    node.next = head;
    return node;
}

---

Complexity

Operation	Time
Insert Head	O(1)

---

C. Reverse Linked List

One of the most important interview questions.

---

Iterative Solution

---

Python

def reverse(head):

    prev = None
    curr = head

    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    return prev

---

Java

Node reverse(Node head) {

    Node prev = null;
    Node curr = head;

    while(curr != null) {

        Node next = curr.next;
        curr.next = prev;

        prev = curr;
        curr = next;
    }

    return prev;
}

---

C++

Node* reverse(Node* head) {

    Node* prev = NULL;
    Node* curr = head;

    while(curr != NULL) {

        Node* next = curr->next;
        curr->next = prev;

        prev = curr;
        curr = next;
    }

    return prev;
}

---

JavaScript

function reverse(head) {

    let prev = null;
    let curr = head;

    while (curr) {

        let next = curr.next;
        curr.next = prev;

        prev = curr;
        curr = next;
    }

    return prev;
}

---

Complexity

Time	Space
O(n)	O(1)

---

4. Fast & Slow Pointer Technique

Very important for interviews.

Used for:

• Find middle

• Detect cycle

• Palindrome list

• Remove nth node

---

Find Middle Node

---

Python

def middle(head):

    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

---

Java

Node middle(Node head) {

    Node slow = head;
    Node fast = head;

    while(fast != null && fast.next != null) {

        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

---

C++

Node* middle(Node* head) {

    Node* slow = head;
    Node* fast = head;

    while(fast && fast->next) {

        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

---

JavaScript

function middle(head) {

    let slow = head;
    let fast = head;

    while (fast && fast.next) {

        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

---

5. Detect Cycle (Floyd’s Algorithm)

Extremely common FAANG question.

---

Python

def has_cycle(head):

    slow = fast = head

    while fast and fast.next:

        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

---

Java

boolean hasCycle(Node head) {

    Node slow = head;
    Node fast = head;

    while(fast != null && fast.next != null) {

        slow = slow.next;
        fast = fast.next.next;

        if(slow == fast)
            return true;
    }

    return false;
}

---

C++

bool hasCycle(Node* head) {

    Node* slow = head;
    Node* fast = head;

    while(fast && fast->next) {

        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
            return true;
    }

    return false;
}

---

JavaScript

function hasCycle(head) {

    let slow = head;
    let fast = head;

    while (fast && fast.next) {

        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast)
            return true;
    }

    return false;
}

---

Complexity

Time	Space
O(n)	O(1)

---

6. Merge Two Sorted Lists

Classic interview problem.

---

Python

def merge(l1, l2):

    dummy = Node(0)
    tail = dummy

    while l1 and l2:

        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next

        tail = tail.next

    tail.next = l1 or l2

    return dummy.next

---

Java

Node merge(Node l1, Node l2) {

    Node dummy = new Node(0);
    Node tail = dummy;

    while(l1 != null && l2 != null) {

        if(l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }

        tail = tail.next;
    }

    tail.next = (l1 != null) ? l1 : l2;

    return dummy.next;
}

---

C++

Node* merge(Node* l1, Node* l2) {

    Node* dummy = new Node(0);
    Node* tail = dummy;

    while(l1 && l2) {

        if(l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }

        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;

    return dummy->next;
}

---

JavaScript

function merge(l1, l2) {

    let dummy = new Node(0);
    let tail = dummy;

    while (l1 && l2) {

        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }

        tail = tail.next;
    }

    tail.next = l1 || l2;

    return dummy.next;
}

---

7. Remove N-th Node From End

Very popular Meta question.

---

Python

def remove_nth(head, n):

    dummy = Node(0)
    dummy.next = head

    slow = fast = dummy

    for _ in range(n + 1):
        fast = fast.next

    while fast:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next

    return dummy.next

---

Java

Node removeNth(Node head, int n) {

    Node dummy = new Node(0);
    dummy.next = head;

    Node slow = dummy;
    Node fast = dummy;

    for(int i = 0; i <= n; i++)
        fast = fast.next;

    while(fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;

    return dummy.next;
}

---

C++

Node* removeNth(Node* head, int n) {

    Node* dummy = new Node(0);
    dummy->next = head;

    Node* slow = dummy;
    Node* fast = dummy;

    for(int i = 0; i <= n; i++)
        fast = fast->next;

    while(fast) {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;

    return dummy->next;
}

---

JavaScript

function removeNth(head, n) {

    let dummy = new Node(0);
    dummy.next = head;

    let slow = dummy;
    let fast = dummy;

    for (let i = 0; i <= n; i++)
        fast = fast.next;

    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;

    return dummy.next;
}

---

8. Most Asked Interview Questions

---

Easy

1. Reverse Linked List

2. Find Middle Node

3. Delete Node

4. Merge Two Lists

5. Remove Duplicates

---

Medium

6. Detect Cycle

7. Palindrome Linked List

8. Remove N-th Node

9. Odd Even Linked List

10. Sort Linked List

---

Hard

11. Reverse Nodes in K Group

12. Merge K Sorted Lists

13. LRU Cache

14. Copy Random Pointer

15. Flatten Doubly Linked List

---

9. Interview Questions and Answers

---

Q1. Why is linked list insertion at head O(1)?

Answer

Because we only change two pointers:

new.next = head
head = new

No shifting is needed.

---

Q2. Why is array access faster than linked list?

Answer

Arrays support direct indexing:

arr[i]

Linked lists require traversal from head.

Thus:

Structure	Access
Array	O(1)
Linked List	O(n)

---

Q3. Explain Floyd Cycle Detection.

Answer

Two pointers move at different speeds.

• Slow → 1 step

• Fast → 2 steps

If a cycle exists, they eventually meet.

---

Q4. Why use Dummy Nodes?

Answer

Dummy nodes simplify:

• Head deletion

• Insertion

• Edge cases

Example:

dummy = Node(0)
dummy.next = head

---

10. Complexity Cheat Sheet

Operation	Time	Space
Traversal	O(n)	O(1)
Search	O(n)	O(1)
Insert Head	O(1)	O(1)
Insert Tail	O(n)	O(1)
Delete	O(n)	O(1)
Reverse	O(n)	O(1)
Detect Cycle	O(n)	O(1)

---

11. Advanced Interview Tips

---

Tip 1: Always Draw the List

Example:

prev -> curr -> next

This reduces pointer bugs.

---

Tip 2: Think About Edge Cases

Always test:

• Empty list

• Single node

• Even length

• Odd length

• Deleting head

• Cycle present

---

Tip 3: Clarify Constraints

Ask interviewer:

• Can we modify the list?

• Is extra memory allowed?

• Should solution be one-pass?

---

12. Most Important Patterns

These patterns solve most interview questions.

---

Pattern 1: Fast & Slow Pointer

Used for:

• Middle node

• Cycle detection

• Palindrome

---

Pattern 2: Reversal

Used in:

• Reverse list

• K-group reversal

• Palindrome

---

Pattern 3: Dummy Node

Used in:

• Merge

• Deletion

• Partition list

---

Pattern 4: Two Pointer Gap

Used in:

• Remove nth node

• Window problems

---

13. Recommended Practice Resources

• LeetCode Linked List Problems

• NeetCode Roadmap

• GeeksforGeeks Linked List Tutorial

• Visualgo Linked List Visualization

---

14. Final FAANG Preparation Advice

To perform well in linked list interviews:

1. Master pointer manipulation

2. Practice writing bug-free code

3. Memorize common patterns

4. Explain complexity clearly

5. Handle edge cases confidently

6. Practice without an IDE

Strong linked list skills are often viewed as a signal of strong problem-solving ability in top-tier software engineering interviews.