Understanding Linked Lists

A Linked List is a linear data structure where elements are stored in nodes. Each node contains a data field and a reference (or link) to the next node in the sequence.

Types of Linked Lists

  1. Singly Linked List: Each node has data and a pointer to the next node.
  2. Doubly Linked List: Each node has data, a pointer to the next node, and a pointer to the previous node.
  3. Circular Linked List: The last node points back to the first node or any other node before it, forming a circle.

Basic Structure of a Singly Linked List Node

Java Implementation

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

C++ Implementation

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

Basic Operations on a Singly Linked List

Let's implement some common operations on a singly linked list:

  1. Insertion at the beginning
  2. Insertion at the end
  3. Deletion of a node
  4. Traversal
  5. Searching for a value

Java Implementation

class LinkedList {
    ListNode head;

    // Insertion at the beginning
    public void insertAtBeginning(int x) {
        ListNode newNode = new ListNode(x);
        newNode.next = head;
        head = newNode;
    }

    // Insertion at the end
    public void insertAtEnd(int x) {
        ListNode newNode = new ListNode(x);
        if (head == null) {
            head = newNode;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Deletion of a node
    public void deleteNode(int key) {
        ListNode temp = head, prev = null;
        if (temp != null && temp.val == key) {
            head = temp.next;
            return;
        }
        while (temp != null && temp.val != key) {
            prev = temp;
            temp = temp.next;
        }
        if (temp == null) return;
        prev.next = temp.next;
    }

    // Traversal
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Searching for a value
    public boolean search(int x) {
        ListNode current = head;
        while (current != null) {
            if (current.val == x) return true;
            current = current.next;
        }
        return false;
    }
}

C++ Implementation

class LinkedList {
private:
    ListNode* head;

public:
    LinkedList() : head(nullptr) {}

    // Insertion at the beginning
    void insertAtBeginning(int x) {
        ListNode* newNode = new ListNode(x);
        newNode->next = head;
        head = newNode;
    }

    // Insertion at the end
    void insertAtEnd(int x) {
        ListNode* newNode = new ListNode(x);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        ListNode* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }

    // Deletion of a node
    void deleteNode(int key) {
        ListNode* temp = head, *prev = nullptr;
        if (temp != nullptr && temp->val == key) {
            head = temp->next;
            delete temp;
            return;
        }
        while (temp != nullptr && temp->val != key) {
            prev = temp;
            temp = temp->next;
        }
        if (temp == nullptr) return;
        prev->next = temp->next;
        delete temp;
    }

    // Traversal
    void printList() {
        ListNode* current = head;
        while (current != nullptr) {
            std::cout << current->val << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // Searching for a value
    bool search(int x) {
        ListNode* current = head;
        while (current != nullptr) {
            if (current->val == x) return true;
            current = current->next;
        }
        return false;
    }
};

Common Interview Questions on Linked Lists

Let's dive deeper into each of the common interview questions mentioned earlier, providing explanations and implementations in both Java and C++.

1. Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list and return the reversed list.

Explanation: This problem tests your ability to manipulate pointers. The idea is to reverse the direction of pointers for each node. We iterate through the list, changing the next pointer of each node to point to the previous node.

Java Implementation

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

C++ Implementation

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* nextTemp = current->next;
        current->next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

2. Detect a Cycle in a Linked List

Problem: Given the head of a linked list, determine if the linked list has a cycle in it.

Explanation: We use Floyd's Cycle-Finding Algorithm, also known as the "tortoise and hare" algorithm. We use two pointers, moving at different speeds. If there's a cycle, the fast pointer will eventually meet the slow pointer.

Java Implementation

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

C++ Implementation

bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

3. Find the Middle Element of a Linked List

Problem: Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Explanation: We use two pointers, where one moves twice as fast as the other. When the fast pointer reaches the end, the slow pointer will be at the middle.

Java Implementation

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

C++ Implementation

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

4. Merge Two Sorted Lists

Problem: Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Explanation: We compare the values of the nodes from both lists and build a new sorted list by choosing the smaller value each time.

Java Implementation

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1 != null) {
        current.next = l1;
    }
    if (l2 != null) {
        current.next = l2;
    }

    return dummy.next;
}

C++ Implementation

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    if (l1 != nullptr) {
        current->next = l1;
    }
    if (l2 != nullptr) {
        current->next = l2;
    }

    return dummy.next;
}

5. Remove Nth Node From End of List

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

Explanation: We use two pointers. We first move the fast pointer n nodes ahead. Then we move both pointers until the fast pointer reaches the end. At this point, the slow pointer will be just before the node we want to remove.

Java Implementation

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;

    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }

    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

C++ Implementation

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *first = &dummy;
    ListNode *second = &dummy;

    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first->next;
    }

    // Move first to the end, maintaining the gap
    while (first != nullptr) {
        first = first->next;
        second = second->next;
    }
    second->next = second->next->next;
    return dummy.next;
}

These problems cover a range of techniques commonly used in linked list manipulations:

  1. Reverse a Linked List: Tests basic pointer manipulation.
  2. Detect a Cycle: Demonstrates the use of the two-pointer technique at different speeds.
  3. Find the Middle Element: Shows how to use the two-pointer technique to find a specific position.
  4. Merge Two Sorted Lists: Tests the ability to compare and construct a new list.
  5. Remove Nth Node From End: Combines the two-pointer technique with a specific counting requirement.

Understanding these problems and their solutions will provide a solid foundation for tackling linked list questions in coding interviews. Remember, the key to solving linked list problems often lies in careful pointer manipulation and sometimes in using multiple pointers moving at different speeds or with different starting points.