DSA: Linked Lists

What are Linked Lists?

Linked lists are a fundamental data structure in computer science used to store collections of elements. Unlike arrays, which store elements in contiguous memory locations, linked lists consist of nodes where each node contains a data element and a reference (or link) to the next node in the sequence. This structure allows for flexible memory utilization and dynamic memory allocation.

Why are Linked Lists Used?

1. Dynamic Size: The size of a linked list can grow or shrink dynamically, so it's more flexible in using memory compared to static data structures like arrays.

2. Ease of Insertions/Deletions: Adding or removing nodes doesn't require the elements to be contiguous in memory, making these operations potentially more efficient than in arrays, where shifting elements is often necessary.

Advantages of Linked Lists over Arrays

1. No Memory Wastage: Arrays allocate memory based on a fixed size. If the allocation is too large, memory is wasted. If too small, resizing is necessary, which is costly. Linked lists, however, allocate memory as needed.

2. Efficient Insertions/Deletions: In a linked list, insertions and deletions can be performed more efficiently because these operations do not require elements to be contiguous in memory.

Disadvantages of Linked Lists compared to Arrays

1. Memory Overhead: Each node in a linked list requires extra memory for storing the pointer to the next node.

2. Access Time: Linked lists do not allow direct access to elements by their position. To access an element, you must traverse the list from the beginning, which can be time-consuming.

3. No Cache Locality: The non-contiguous storage of linked lists can lead to poor cache performance compared to arrays, which can significantly impact performance.

Singly Linked List

Here's a simple representation of a singly linked list with three nodes:

              [Node1]       [Node2]       [Tail]
             +----+----+  +----+----+    +----+----+
             | 20 |    |->| 40 |    |->  | 60 |    |-> null
             +----+----+  +----+----+    +----+----+

• Node: Each node contains two parts:

  • Data: The actual value stored (e.g., 20, 40, 60).

  • Next: A pointer to the next node in the list.

• Tail: The last node of the list which points to null, indicating the end of the list.

Doubly Linked List

A doubly linked list is an extension of the singly linked list, where each node contains an additional link field pointing to the previous node in the sequence. This two-way linkage allows traversal of the list in both directions, making some operations more efficient, particularly deletions and insertions at both ends and in the middle of the list.

Here's a representation of a doubly linked list with three nodes:

                     [Node1/Head]          [Node2]             [Node3/Tail]           
                         |                   |                   |                    
                         V                   V                   V                    
                       +--------+          +--------+          +--------+            
                       |  Next  | -------->|  Next  | -------->|  Next  | --------> null
        null <-------- |  Prev  | <--------|  Prev  | <--------|  Prev  | 
                       +--------+          +--------+          +--------+             
                       |  Data  |          |  Data  |          |  Data  |
                       |   20   |          |   40   |          |   60   |
                       +--------+          +--------+          +--------+

1. Nodes (Node1/Head, Node2, Node3/Tail):

   • Each node in the list consists of three main components:

     • Prev: Points to the previous node in the list.

     • Next: Points to the next node in the list.

     • Data: Holds the actual data value (20, 40, 60).

2. Links:

   • Next Link: This arrow points from the "Next" part of one node to the "Next" part of the following node. It shows the direction to the next node in the list.

   • Prev Link: This arrow points from the "Prev" part of one node to the "Prev" part of the preceding node, illustrating the connection back to the previous node.

3. Boundaries:

   • null Pointers:

     • The "Prev" pointer of the first node (Node1/Head) points to null, indicating that there is no node before it.

     • The "Next" pointer of the last node (Node3/Tail) points to null, indicating that there is no node after it.

The doubly linked list allows for easier deletion of a node (as no predecessor is needed), and efficient insertion operations before or after a given node, enhancing versatility compared to singly linked lists.

To transform a singly or doubly linked list into a circular linked list, you need to modify the way the nodes are linked so that the list forms a continuous loop. Here's how you can make these modifications:

Singly Linked Circular List

In a singly linked circular list, the "Next" pointer of the last node is modified to point back to the first node instead of pointing to null. This creates a loop, allowing for continuous traversal of the list.

Modification Steps:

1. Identify the Tail: Find the last node of the list, which would typically have its "Next" pointer set to null.

2. Link to Head: Change the "Next" pointer of this last node to point to the head of the list instead of null.

This creates a circular structure where you can start at any node and eventually return to that starting point by continuously following the "Next" pointers.

Doubly Linked Circular List

A doubly linked circular list not only links the last node back to the first node but also links the first node back to the last node. This allows for seamless bidirectional traversal.

Modification Steps:

1. Identify the Tail and Head: Find the last node (Tail) and the first node (Head) of the list.

2. Link Tail to Head: Change the "Next" pointer of the Tail to point to the Head.

3. Link Head to Tail: Change the "Prev" pointer of the Head to point to the Tail.

This modification ensures that the list forms a complete loop, allowing navigation from any node to any other node in both forward and backward directions without ever encountering a null pointer.

Here's a simple visualization of both types:

Singly Linked Circular List:

   [Head] ---> [Node2] ---> [Node3] ---> [Tail]
     ^                                      |
     |______________________________________|

Doubly Linked Circular List:

   [Head] <--> [Node2] <--> [Node3] <--> [Tail]
     ^                                          ^
     |__________________________________________|

Practical Usage

Circular linked lists are particularly useful in applications where the data naturally forms a cycle, such as:

• Implementing round-robin scheduling algorithms.

• Creating a continuously looping playlist or slideshow.

• Managing applications where resources need to be recycled in a fixed, repetitive order.

These modifications allow for easier management of such cyclic data structures, avoiding special cases for the end of the list in many operations, which can simplify coding and reduce error potential.

Singly linked lists are dynamic data structures that consist of nodes linked together by pointers. Here's a breakdown of common operations on singly linked lists, each accompanied by sample C code:

Node Structure Definition

First, define the structure of a node in the linked list:

typedef struct Node {
    int data;
    struct Node* next;
} Node;

1. Creating a New Node

Function to create a new node with given data:

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

2. Insertion at the Head

Inserts a new node at the beginning of the list:

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

3. Insertion at the Tail

Inserts a new node at the end of the list:

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

4. Insertion in the Middle

Inserts a new node after a given node:

void insertAfterNode(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("The given previous node cannot be NULL\n");
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

5. Deletion at the Head

Deletes the first node of the list:

void deleteAtHead(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

6. Deletion at the Tail

Deletes the last node of the list:

void deleteAtTail(Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    free(current->next);
    current->next = NULL;
}

7. Deletion in the Middle

Deletes a node after a given node:

void deleteAfterNode(Node* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) return;
    Node* temp = prevNode->next;
    prevNode->next = temp->next;
    free(temp);
}

8. Searching for a Node

Searches for a node containing a specific data:

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL; // return NULL if the key is not found
}

9. Length of List

This function counts the number of nodes in the list:

int listLength(Node* head) {
    int count = 0;
    Node* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

10. Reverse the List

This function reverses the order of nodes in the list:

void reverseList(Node** head) {
    Node* prev = NULL;
    Node* current = *head;
    Node* next = NULL;
    while (current != NULL) {
        next = current->next;  // store next node
        current->next = prev;  // reverse current node's pointer
        prev = current;        // move pointers one position ahead
        current = next;
    }
    *head = prev; // Reset head to the new first element
}

11. Sort the List

This function sorts the list using the simple bubble sort algorithm, which is suitable for educational purposes but not the most efficient for large lists:

void sortList(Node** head) {
    int swapped;
    Node* ptr1;
    Node* lptr = NULL;

    // Checking for empty list
    if (*head == NULL)
        return;

    do {
        swapped = 0;
        ptr1 = *head;

        while (ptr1->next != lptr) {
            if (ptr1->data > ptr1->next->data) {
                int temp = ptr1->data;
                ptr1->data = ptr1->next->data;
                ptr1->next->data = temp;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

Below are implementations for various common operations on doubly linked lists in C, including node creation, insertion, deletion, searching, and additional operations such as finding the length of the list, reversing the list, and sorting the list. Each function is designed considering the structure where the list starts from the first node directly without a separate head structure.

Node Structure Definition

First, let's define the structure of a node in a doubly linked list:

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

1. Creating a New Node

Function to create a new node with given data:

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

2. Insertion at the Head

Inserts a new node at the beginning of the list:

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

3. Insertion at the Tail

Inserts a new node at the end of the list:

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* tail = *head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = newNode;
    newNode->prev = tail;
}

4. Insertion in the Middle

Inserts a new node after a given node:

void insertAfterNode(Node* prevNode, int data) {
    if (!prevNode) {
        printf("The given previous node cannot be NULL\n");
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
}

5. Deletion at the Head

Deletes the first node of the list:

void deleteAtHead(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
}

6. Deletion at the Tail

Deletes the last node of the list:

void deleteAtTail(Node** head) {
    if (*head == NULL) return;
    Node* tail = *head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    if (tail->prev != NULL) {
        tail->prev->next = NULL;
    } else {
        *head = NULL; // The list had only one node
    }
    free(tail);
}

7. Deletion in the Middle

Deletes a node after a given node:

void deleteAfterNode(Node* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) return;
    Node* temp = prevNode->next;
    prevNode->next = temp->next;
    if (temp->next != NULL) {
        temp->next->prev = prevNode;
    }
    free(temp);
}

8. Searching for a Node

Searches for a node containing a specific data:

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL; // return NULL if the key is not found
}

9. Length of List

This function counts the number of nodes in the list:

int listLength(Node* head) {
    int count = 0;
    Node* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

10. Reverse the List

This function reverses the order of nodes in the list:

void reverseList(Node** head) {
    Node* temp = NULL;
    Node* current = *head;
    // Swap next and prev for all nodes of the list
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    // Adjust head pointer
    if (temp != NULL) {
        *head = temp->prev;
    }
}

11. Sort the List

This function sorts the list using a simple bubble sort algorithm:

void sortList(Node** head) {
    int swapped;
    Node* ptr1;
    Node* lptr = NULL;
    if (*head == NULL) return;

    do {
        swapped = 0;
        ptr1 = *head;

        while (ptr1->next != lptr) {
            if (ptr1->data > ptr1->next->data) {
                int temp = ptr1->data;
                ptr1->data = ptr1->next->data;
                ptr1->next->data = temp;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

For circular linked lists, both singly and doubly linked, some operations require slight modifications due to the cyclical nature of the lists. Below, I'll provide C code for searching, sorting, reversing, and finding the length for both singly and doubly circular linked lists.

Singly Circular Linked List

1. Length of List

int circularListLength(Node* head) {
    if (head == NULL) return 0;
    Node* current = head;
    int count = 0;
    do {
        count++;
        current = current->next;
    } while (current != head);
    return count;
}

2. Search for a Node

Node* circularSearch(Node* head, int key) {
    if (head == NULL) return NULL;
    Node* current = head;
    do {
        if (current->data == key) return current;
        current = current->next;
    } while (current != head);
    return NULL;
}

3. Reverse the List

void reverseCircularList(Node** head) {
    if (*head == NULL || (*head)->next == *head) return; // Single node or empty list
    Node *prev = NULL, *current = *head, *next;
    do {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    } while (current != *head);

    (*head)->next = prev;
    *head = prev;
}

4. Sort the List

Sorting a singly circular linked list in-place is more complex. Here, I'll show a simple bubble sort:

void sortCircularList(Node** head) {
    if (*head == NULL || (*head)->next == *head) return;
    int swapped;
    Node *ptr1;
    Node *lptr = NULL;
    do {
        swapped = 0;
        ptr1 = *head;
        do {
            if (ptr1->data > ptr1->next->data) {
                int temp = ptr1->data;
                ptr1->data = ptr1->next->data;
                ptr1->next->data = temp;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        } while (ptr1->next != lptr && ptr1->next != *head);
        lptr = ptr1;
    } while (swapped);
}

Doubly Circular Linked List

1. Length of List

int circularDoublyListLength(Node* head) {
    return circularListLength(head); // Same as singly circular linked list
}

2. Search for a Node

Node* circularDoublySearch(Node* head, int key) {
    return circularSearch(head, key); // Same as singly circular linked list
}

3. Reverse the List

void reverseDoublyCircularList(Node** head) {
    if (*head == NULL || (*head)->next == *head) return; // Single node or empty list
    Node *current = *head;
    Node *temp = NULL;
    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = current->prev; // previously 'next' before we swapped
    } while (current != *head);

    *head = (*head)->next; // New head is the old tail
}

4. Sort the List

Sorting a doubly circular linked list can use the same logic as for singly circular, but with added support for previous pointers:

void sortDoublyCircularList(Node** head) {
    sortCircularList(head); // Same sorting logic can be applied
    // Fix the previous pointers after sorting
    if (*head == NULL || (*head)->next == *head) return;
    Node* current = (*head)->next;
    do {
        current->prev = current->prev->next;
        current = current->next;
    } while (current != *head);
}

Problems:

Beginner Level

1. Implement a Singly Linked List - Create a basic linked list with operations to add and remove nodes.

2. Print Elements of a Linked List - Write a function that prints out all the elements of a linked list.

3. Insert a Node at the Tail of a Linked List - Write a function that inserts a new node at the end of the list.

4. Delete a Node from a Linked List - Implement a function that can remove a given node from a linked list.

5. Count Nodes - Create a function that returns the count of nodes present in the linked list.

Intermediate Level

6. Detect Loop in a Linked List - Implement an algorithm to detect a cycle in a linked list.

7. Reverse a Linked List - Write a function that reverses the links in a linked list.

8. Find the Middle of a Linked List - Develop a method to find the middle node of a linked list efficiently.

9. Remove N-th Node from End - Remove the N-th node from the end of the list in a single pass.

10. Merge Two Sorted Linked Lists - Merge two sorted linked lists into a single, sorted linked list.

Advanced Level

11. Detect and Remove Loop - Detect a cycle in a linked list and remove it.

12. Rotate a Linked List - Rotate the linked list right by k places.

13. Clone a Linked List with Random Pointer - Clone a linked list where each node has a next and a random pointer.

14. Add Two Numbers Represented by Linked Lists - Given two numbers represented by two lists, write a function that returns the sum list.

15. Sort a Linked List - Implement a sorting algorithm to sort a linked list (e.g., merge sort).

Expert Level

16. Find the Intersection Point of Two Linked Lists - Determine the node where two singly linked lists intersect.

17. Palindrome Linked List - Check if a linked list forms a palindrome.

18. Rearrange a Linked List - Rearrange the linked list in a specific pattern (e.g., L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …).

19. Partition List - Partition the list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

20. Multi-level Doubly Linked List Flattening - Flatten a multi-level doubly linked list where in addition to the next and previous pointers, each node has a child pointer, which may point to a separate doubly linked list.

Below are hints on how to approach each linked list problem in C, categorized by difficulty level:

Beginner Level

1. Implement a Singly Linked List: Begin by defining a struct Node containing an int data field and a Node* next pointer. Implement functions to create a node, insert a node, and display the list. Pay attention to special cases like inserting into an empty list.

2. Print Elements of a Linked List: Use a simple traversal technique. Start from the head and use a while loop to go through each node until you reach NULL. In each iteration, print the data of the current node.

3. Insert a Node at the Tail of a Linked List: Traverse the list from the head until you reach the last node, which is identified by its next pointer being NULL. Create a new node and link it to the last node's next.

4. Delete a Node from a Linked List: Consider two cases: deleting the head node and deleting any other node. For the latter, traverse to the node immediately before the target node, then change its next pointer to skip the target node.

5. Count Nodes: Start from the head and use a counter variable. Traverse through each node, incrementing the counter until you reach the end of the list (NULL). Return the counter value.

Intermediate Level

6. Detect Loop in a Linked List: Implement Floyd’s Cycle-Finding Algorithm, also known as the tortoise and the hare approach. Use two pointers, one moving twice as fast as the other; if they meet, a loop exists.

7. Reverse a Linked List: Use three pointers: previous, current, and next. Initialize previous to NULL and current to the head. In a loop, move current along the list, adjust its next to point to previous, and then update previous and current.

8. Find the Middle of a Linked List: Use two pointers, one moving twice as fast as the other (slow and fast pointers). By the time the fast pointer reaches the end, the slow pointer will be at the middle.

9. Remove N-th Node from End: Use two pointers with a gap of n nodes between them. Move both pointers simultaneously until the fast one reaches the end, then modify pointers to remove the target node.

10. Merge Two Sorted Linked Lists: Use a dummy head and a tail pointer starting at this dummy. Compare nodes from both lists, appending the smaller one to the tail, and advance in that list. Continue until all nodes are consumed.

Advanced Level

11. Detect and Remove Loop: Detect a loop using Floyd’s Cycle-Finding Algorithm. Once detected, use two pointers to find the start of the loop and then adjust pointers to break the loop.

12. Rotate a Linked List: Compute the length of the list, adjust k to be within the length if it’s greater, find the k-th last node, make it the new head, and adjust the next pointers to form a proper circular list, then break the circle at the new end.

13. Clone a Linked List with Random Pointer: Use a hashmap to map original nodes to their clones. First, create the clone nodes with next pointers set. Second, set the random pointers using the hashmap.

14. Add Two Numbers Represented by Linked Lists: Traverse both lists, adding corresponding digits along with any carry, creating new nodes for the sum list. Handle remaining digits and carry after one list is exhausted.

15. Sort a Linked List: Implement merge sort due to its efficiency with linked lists. Split the list into halves, recursively sort both halves, and merge them.

Expert Level

16. Find the Intersection Point of Two Linked Lists: First, get the lengths of both lists. Advance the start of the longer list by the difference in lengths, then move in both lists simultaneously until the nodes match.

17. Palindrome Linked List: Split the list into two halves, reverse the second half, and then compare node by node. Optionally, reverse the second half again to restore the original list.

18. Rearrange a Linked List: Find the middle of the list, split into two lists, reverse the second list, and alternately merge nodes from each list.

19. Partition List: Create two new lists, one for nodes less than x and one for nodes greater or equal to x. Traverse the original list, partitioning the nodes into the two new lists, then merge these lists.

20. Multi-level Doubly Linked List Flattening: Use a stack or recursion to handle child nodes. Traverse the main level nodes and whenever a child node is encountered, recursively flatten and merge it into the main list.

Solution:

Beginner Level

1. Implement a Singly Linked List

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a linked list node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node with given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Allocate memory for a new node
    if (newNode == NULL) { // Check if memory allocation failed
        printf("Memory allocation failed.\n");
        exit(1); // Exit if memory cannot be allocated
    }
    newNode->data = data; // Set the node's data
    newNode->next = NULL; // Initialize the next pointer to NULL
    return newNode; // Return the new node
}

// Function to insert a node at the head of the list
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data); // Create a new node
    newNode->next = *head; // Point the new node's next to the current head
    *head = newNode; // Update head to the new node
}

// Function to print all elements in the linked list
void printList(Node* head) {
    Node* current = head; // Start from the head
    while (current != NULL) { // Traverse until the end of the list
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n"); // Print NULL at the end of the list
}

int main() {
    Node* head = NULL; // Start with an empty list
    insertAtHead(&head, 10); // Insert 10 into the list
    insertAtHead(&head, 20); // Insert 20 into the list
    insertAtHead(&head, 30); // Insert 30 into the list
    printList(head); // Output the list
    return 0;
}

2. Print Elements of a Linked List

// This function is included in the above example as `printList`.
// Refer to the `printList` function in the "Implement a Singly Linked List" code.

3. Insert a Node at the Tail of a Linked List

// Function to insert a node at the tail of the list
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data); // Create a new node
    if (*head == NULL) { // If the list is empty, make this the head node
        *head = newNode;
    } else {
        Node* last = *head; // Find the last node
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = newNode; // Append the new node at the end
    }
}

4. Delete a Node from a Linked List

// Function to delete a node from the list
void deleteNode(Node** head, int key) {
    Node* temp = *head, *prev = NULL;
    if (temp != NULL && temp->data == key) { // If the head needs to be removed
        *head = temp->next; // Change head
        free(temp); // Free old head
        return;
    }
    // Find the node to be deleted
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // If the key was not present
    prev->next = temp->next; // Unlink the node from the list
    free(temp); // Free memory
}

5. Count Nodes

// Function to count the number of nodes in the list
int getCount(Node* head) {
    int count = 0; // Initialize count
    Node* current = head; // Initialize current
    while (current != NULL) { // Iterate over the list
        count++;
        current = current->next;
    }
    return count; // Return the count
}

Intermediate Level

6. Detect Loop in a Linked List

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect a loop using Floyd’s Cycle-Finding Algorithm
int detectLoop(Node* head) {
    Node* slow_p = head, *fast_p = head; // Use two pointers, slow and fast
    while (slow_p && fast_p && fast_p->next) {
        slow_p = slow_p->next; // Move slow by 1
        fast_p = fast_p->next->next; // Move fast by 2
        if (slow_p == fast_p) { // Check if the two pointers meet
            return 1; // Loop found
        }
    }
    return 0; // No loop
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = head; // Creating a loop for demonstration

    if (detectLoop(head)) {
        printf("Loop found\n");
    } else {
        printf("No loop\n");
    }
    return 0;
}

7. Reverse a Linked List

// Function to reverse a linked list
void reverseList(Node** head) {
    Node* prev = NULL;
    Node* current = *head;
    Node* next = NULL;
    while (current != NULL) {
        next = current->next;  // Store next node
        current->next = prev;  // Reverse current node's pointer
        prev = current;        // Move pointers one position ahead
        current = next;
    }
    *head = prev; // Reset head to new first element
}

int main() {
    Node* head = NULL;
    // Assuming insertAtTail and createNode are defined and work correctly
    // Reuse functions from previous problems
    // Use the reverseList function to reverse the linked list
    // Print the list to verify reversal
    return 0;
}

8. Find the Middle of a Linked List

// Function to find the middle of a linked list
Node* findMiddle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    if (head != NULL) {
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next; // move slow by 1
            fast = fast->next->next; // move fast by 2
        }
    }
    return slow; // slow is now pointing at the middle node
}

int main() {
    Node* head = NULL;
    // Assuming insertAtTail and createNode are defined and work correctly
    // Use the findMiddle function to find the middle of the linked list
    // Print the data of the middle node
    return 0;
}

9. Remove N-th Node from End

// Function to remove the N-th node from the end of the list
void removeNthFromEnd(Node** head, int n) {
    Node* first = *head;
    Node* second = *head;
    for (int i = 0; i < n; ++i) { // Move first n steps ahead
        if (first == NULL) return; // n is larger than the number of nodes
        first = first->next;
    }
    if (first == NULL) { // If first is NULL, n is the length of the list
        *head = (*head)->next; // Remove head
        return;
    }
    while (first->next != NULL) {
        first = first->next;
        second = second->next;
    }
    Node* temp = second->next;
    second->next = temp->next; // Bypass the n-th node
    free(temp);
}

int main() {
    Node* head = NULL;
    // Assuming insertAtTail and createNode are defined and work correctly
    // Use the removeNthFromEnd function to remove the N-th node from the end of the linked list
    // Print the list to verify removal
    return 0;
}

10. Merge Two Sorted Linked Lists

// Function to merge two sorted linked lists
Node* mergeSortedLists(Node* l1, Node* l2) {
    Node dummy; // Create a dummy node to

 form the base of the new list
    Node* tail = &dummy; // Tail points to the last node of the new list
    dummy.next = NULL;
    while (l1 != NULL && l2 != NULL) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = (l1 != NULL) ? l1 : l2; // Attach the remaining part
    return dummy.next; // Return the next of dummy as the head of the new list
}

int main() {
    Node* list1 = NULL;
    Node* list2 = NULL;
    // Assuming insertAtTail and createNode are defined and work correctly
    // Use the mergeSortedLists function to merge two sorted linked lists
    // Print the merged list
    return 0;
}

Advanced Level

11. Detect and Remove Loop

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect and remove a loop in a linked list
void detectAndRemoveLoop(Node* head) {
    Node *slow = head, *fast = head;
    // Step 1: Use Floyd's Cycle detection algorithm to find the loop
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) { // Loop detected
            break;
        }
    }

    // Step 2: If a loop was found, remove the loop
    if (slow == fast) {
        slow = head;
        // Move slow to head. Keep fast at meeting point. Each are k steps from the loop start
        while (slow->next != fast->next) { // Find the start of the loop
            slow = slow->next;
            fast = fast->next;
        }
        fast->next = NULL; // Remove loop
    }
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = head->next; // Create a loop for demonstration

    detectAndRemoveLoop(head);
    // Function to print list would go here, showing that loop is gone
    return 0;
}

12. Rotate a Linked List

// Function to rotate a linked list right by k places
void rotateList(Node** head, int k) {
    if (*head == NULL || k == 0) return;

    // Compute the size of the linked list
    Node *current = *head;
    int len = 1;
    while (current->next != NULL) {
        len++;
        current = current->next;
    }
    // Make the list circular
    current->next = *head;

    // Find the point to break the loop
    k = k % len;
    int stepsToNewHead = len - k;
    while (stepsToNewHead--) current = current->next;

    // Set new head and break the loop
    *head = current->next;
    current->next = NULL;
}

int main() {
    Node* head = NULL;
    // Assuming createNode and append functions defined and correctly work
    // Use the rotateList function to rotate the linked list right by k places
    // Print the list to verify rotation
    return 0;
}

13. Clone a Linked List with Random Pointer

#include <stdio.h>
#include <stdlib.h>

typedef struct RandomNode {
    int data;
    struct RandomNode* next;
    struct RandomNode* random;
} RandomNode;

// Function to clone a linked list with a random pointer
RandomNode* cloneRandomList(RandomNode* head) {
    RandomNode* iter = head, *front = head;
    // First round: make copy of each node,
    // and link them together side-by-side in a single list.
    while (iter != NULL) {
        front = iter->next;
        RandomNode* copy = (RandomNode*)malloc(sizeof(RandomNode));
        copy->data = iter->data;
        iter->next = copy;
        copy->next = front;
        iter = front;
    }

    // Second round: assign random pointers for the copy nodes.
    iter = head;
    while (iter != NULL) {
        if (iter->random != NULL) {
            iter->next->random = iter->random->next;
        }
        iter = iter->next->next;
    }

    // Third round: restore the original list, and extract the copy list.
    iter = head;
    RandomNode* pseudoHead = (RandomNode*)malloc(sizeof(RandomNode));
    RandomNode* copy = pseudoHead;
    while (iter != NULL) {
        front = iter->next->next;
        // extract the copy
        copy->next = iter->next;
        copy = copy->next;
        // restore the original list
        iter->next = front;
        iter = front;
    }
    return pseudoHead->next;
}

int main() {
    // Assume code to create a list with random pointers and print functions are available
    // Use the cloneRandom

List function to clone the list and print both to verify
    return 0;
}

14. Add Two Numbers Represented by Linked Lists

// Function to add two numbers represented by linked lists
Node* addTwoLists(Node* first, Node* second) {
    Node* result = NULL;
    Node** lastPtrRef = &result;
    int carry = 0, sum;

    while (first != NULL || second != NULL || carry != 0) {
        int firstVal = (first != NULL) ? first->data : 0;
        int secondVal = (second != NULL) ? second->data : 0;
        sum = firstVal + secondVal + carry;
        carry = sum / 10; // Update carry for next calculation
        Node* temp = createNode(sum % 10); // Create a new node with the sum
        *lastPtrRef = temp;
        lastPtrRef = &(temp->next);

        if (first != NULL) first = first->next;
        if (second != NULL) second = second->next;
    }
    return result;
}

int main() {
    Node* first = NULL;
    Node* second = NULL;
    // Assume that both lists are created and numbers are added in reverse order
    // Use the addTwoLists function to add numbers and print the result
    return 0;
}

15. Sort a Linked List

// Function to sort a linked list using merge sort
Node* mergeSortList(Node* head) {
    if (head == NULL || head->next == NULL) return head;
    Node* middle = findMiddle(head); // Function to find middle of the list
    Node* nextOfMiddle = middle->next;
    middle->next = NULL;

    Node* left = mergeSortList(head);
    Node* right = mergeSortList(nextOfMiddle);

    return mergeSortedLists(left, right); // Function to merge two sorted lists
}

int main() {
    Node* head = NULL;
    // Assuming createNode and other utility functions defined and work correctly
    // Use the mergeSortList function to sort the list and print results
    return 0;
}

Expert Level

16. Find the Intersection Point of Two Linked Lists

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to get the count of nodes in a linked list
int getCount(Node* head) {
    Node* current = head;
    int count = 0;

    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

// Function to get intersection node of two linked lists
Node* getIntersectionNode(Node* head1, Node* head2) {
    int c1 = getCount(head1);
    int c2 = getCount(head2);
    int d;

    if (c1 > c2) {
        d = c1 - c2;
        return _getIntersectionNode(d, head1, head2);
    } else {
        d = c2 - c1;
        return _getIntersectionNode(d, head2, head1);
    }
}

// Helper function to find the intersection node
Node* _getIntersectionNode(int d, Node* head1, Node* head2) {
    Node* current1 = head1;
    Node* current2 = head2;

    for (int i = 0; i < d; i++) {
        if (current1 == NULL) {
            return NULL;
        }
        current1 = current1->next;
    }

    while (current1 != NULL && current2 != NULL) {
        if (current1 == current2)
            return current1;

        current1 = current1->next;
        current2 = current2->next;
    }

    return NULL;
}

int main() {
    // Assume lists are created and possibly intersect
    // Example code to create lists would go here
    return 0;
}

17. Palindrome Linked List

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// Function to check if a linked list is a palindrome
int isPalindrome(Node* head) {
    Node* slow = head, *fast = head;
    Node* second_half, *prev_of_slow = head;
    Node* midnode = NULL;  // To handle odd size list
    int res = 1; // Initialize result

    if (head != NULL && head->next != NULL) {
        // Get the middle of the list
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            prev_of_slow = slow;
            slow = slow->next;
        }

        // For odd sized lists
        if (fast != NULL) {
            midnode = slow;
            slow = slow->next;
        }

        // Reverse the second half of the list
        second_half = reverseList(slow);
        // Check for palindrome
        res = compareLists(head, second_half);

        // Restore the original list
        second_half = reverseList(second_half);
        if (midnode != NULL) {
            prev_of_slow->next = midnode;
            midnode->next = second_half;
        } else {
            prev_of_slow->next = second_half;
        }
    }
    return res;
}

// Helper function to compare two halves
int compareLists(Node* head1, Node* head2) {
    Node* temp1 = head1;
    Node* temp2 = head2;

    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->data == temp2->data) {
            temp1 = temp1->next;
            temp2 = temp2->next;
        } else {
            return 0;
        }
    }

    if (temp1 == NULL && temp2 == NULL)
        return 1;

    return 0;
}

int main() {
    // Assume list is created and functions to populate it are defined
    return 0;
}

18. Rearrange a Linked List

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to

 rearrange a linked list L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
void rearrangeList(Node* head) {
    if (!head || !head->next) return;

    // Step 1: Split the linked list into two halves
    Node* slow = head, *fast = slow->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* head1 = head;
    Node* head2 = slow->next;
    slow->next = NULL;

    // Step 2: Reverse the second half
    head2 = reverseList(head2);

    // Step 3: Merge the two halves
    Node* p1 = head1;
    Node* p2 = head2;
    while (p2) {
        Node* temp = p1->next;
        p1->next = p2;
        p2 = p2->next;
        p1->next->next = temp;
        p1 = temp;
    }
}

int main() {
    // Assume list is created and functions to populate it are defined
    return 0;
}

19. Partition List

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to partition a list around a value x
Node* partition(Node* head, int x) {
    Node* smallerHead = NULL, *smallerLast = NULL;
    Node* greaterLast = NULL, *greaterHead = NULL;
    Node* equalHead = NULL, *equalLast = NULL;

    // Partition the list into three lists: smaller, equal and greater
    while (head != NULL) {
        if (head->data < x) {
            if (smallerHead == NULL) {
                smallerHead = smallerLast = head;
            } else {
                smallerLast->next = head;
                smallerLast = head;
            }
        } else if (head->data == x) {
            if (equalHead == NULL) {
                equalHead = equalLast = head;
            } else {
                equalLast->next = head;
                equalLast = head;
            }
        } else {
            if (greaterHead == NULL) {
                greaterHead = greaterLast = head;
            } else {
                greaterLast->next = head;
                greaterLast = head;
            }
        }
        head = head->next;
    }

    // Merge three lists: smaller, equal and greater
    if (greaterLast != NULL) {
        greaterLast->next = NULL;
    }
    if (smallerHead == NULL) {
        if (equalHead == NULL) {
            return greaterHead;
        }
        equalLast->next = greaterHead;
        return equalHead;
    }
    if (equalHead == NULL) {
        smallerLast->next = greaterHead;
    } else {
        smallerLast->next = equalHead;
        equalLast->next = greaterHead;
    }
    return smallerHead;
}

int main() {
    // Assume list is created and functions to populate it are defined
    return 0;
}

20. Multi-level Doubly Linked List Flattening

#include <stdio.h>
#include <stdlib.h>

typedef struct MultiNode {
    int data;
    struct MultiNode* next;
    struct MultiNode* prev;
    struct MultiNode* child;
} MultiNode;

// Helper function to flatten the list recursively
MultiNode* flattenList(MultiNode* head) {
    MultiNode* current = head;
    MultiNode* tail = head;
    while (current) {
        MultiNode* child = current->child;
        MultiNode* next = current->next;
        if (child) {
            MultiNode* _tail = flattenList(child);
            _tail->next = next;
            if (next) next->prev = _tail;
            current->next = child;
            child->prev = current;
            current->child = NULL;
            tail = _tail;
        } else {
            tail = current;
        }
        current = next;
    }
    return tail;
}

int main() {
    // Assume multi-level list is created and the function to populate it is defined
    return 0;
}

Frequency of Linked List Questions

In technical interviews, especially for positions involving software development, data structures and algorithms are a major focus. Linked lists are one of several key data structures (alongside arrays, trees, graphs, stacks, and queues). A reasonable estimate might be that linked list questions could constitute around 10-15% of data structure-related questions in an interview, especially for roles focused on backend development or systems programming where efficient data manipulation and understanding of memory are crucial.

Common Linked List Interview Questions

Here are some common linked list questions and an approximate estimate of their prevalence in interviews:

1. Reverse a Linked List - (3%)

   • Given a singly or doubly linked list, write a function to reverse the list.

   • Tests basic linked list manipulation and understanding of pointers.

2. Detect a Cycle in a Linked List (Floyd’s Cycle Detection) - (2%)

   • Implement an algorithm to determine if a linked list has a cycle. If it does, find the starting point of the loop.

   • This problem is critical for understanding two-pointer techniques and their applications.

3. Merge Two Sorted Linked Lists - (2%)

   • Write a function that merges two sorted linked lists into a single sorted linked list.

   • Tests the ability to manipulate multiple pointers in linked structures effectively.

4. Remove N-th Node From End of List - (1.5%)

   • Implement a function to remove the N-th node from the end of a singly linked list in one pass.

   • A practical problem that tests efficient pointer manipulation and understanding of list traversal.

5. Palindrome Linked List - (1%)

   • Determine if a linked list is a palindrome.

   • This problem checks for understanding of multiple data structure manipulations, including reversing a list or using a stack.

6. Find Intersection Point of Two Linked Lists - (1%)

   • Write a program to find the node at which the intersection of two singly linked lists begins.

   • A deeper problem that requires an efficient solution beyond the brute-force approach.

7. Add Two Numbers Represented by Linked Lists - (1%)

   • You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

   • Combines elementary arithmetic with linked list manipulation, testing comprehensive understanding of data structures.