Linked List Problem Solving in C

Introduction to Linked Lists in C

A linked list is a linear data structure where each element is a separate object called a node. Each node contains:

Data - The actual value stored
Pointer - Address of the next node

Unlike arrays, linked lists are dynamic in size and efficient for insertions/deletions.

Basic Structure in C:

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

1. Basic Operations

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Create and traverse a linked list	Easy	-	Link
2	Insert node at beginning/end	Easy	-	Link
3	Delete node from linked list	Easy	-	Link
4	Find length of linked list	Easy	Link	-
5	Search an element in linked list	Easy	Link	-
6	Reverse a linked list (Iterative)	Easy	-	Link

2. Reversal Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Reverse a linked list (Iterative)	Easy	Link	Link
2	Reverse a linked list (Recursive)	Medium	Link	Link
3	Reverse linked list in groups of K	Medium	Link	-
4	Reverse alternating K nodes	Medium	Link	-
5	Reverse nodes between positions	Hard	Link	-

3. Cycle Detection

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Detect cycle in linked list	Easy	Link	Link
2	Find start node of cycle	Medium	Link	Link
3	Find length of cycle	Medium	Link	-
4	Remove cycle from linked list	Medium	Link	-

4. Merge Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Merge two sorted linked lists	Easy	Link	Link
2	Merge K sorted linked lists	Medium	Link	-
3	Merge sort for linked lists	Medium	Link	-
4	Merge two lists alternately	Hard	Link	-

5. Intersection Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Find intersection of two lists	Easy	Link	Link
2	Find intersection with cycles	Medium	Link	-

6. Palindrome Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Check if linked list is palindrome	Easy	Link	Link
2	Longest palindromic list	Medium	Link	-

7. Advanced Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	LRU Cache implementation	Hard	Link	-
2	Flatten a multilevel linked list	Hard	Link	-
3	Clone a linked list with random pointer	Hard	Link	-

8. Doubly Linked List Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Implement doubly linked list	Easy	-	Link
2	Reverse doubly linked list	Medium	Link	-
3	Flatten a multilevel doubly linked list	Medium	Link	-
4	Design browser history (using DLL)	Hard	Link	-

9. Circular Linked List Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	Implement circular linked list	Easy	-	Link
2	Detect loop in circular list	Medium	-	Link
3	Split circular list into two halves	Medium	-	Link
4	Josephus Circle using circular list	Hard	-	Link

10. Advanced Problems

S.No	Problem Statement	Difficulty	LeetCode	GeeksforGeeks
1	LRU Cache implementation	Hard	Link	-
2	Clone a linked list with random pointer	Hard	Link	-

C Implementation Examples

Doubly Linked List Implementation

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

// Node structure for doubly linked list
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Create new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

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

// Print list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Circular Linked List Implementation

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

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

// Create circular list
struct Node* createCircularList(int arr[], int n) {
    if (n == 0) return NULL;
    
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = arr[0];
    struct Node* tail = head;
    
    for (int i = 1; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = arr[i];
        tail->next = newNode;
        tail = newNode;
    }
    
    tail->next = head; // Make it circular
    return head;
}

// Print circular list
void printCircularList(struct Node* head) {
    if (head == NULL) return;
    
    struct Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

C Implementation Examples

Basic Linked List Structure in C

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

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to print linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    // Create nodes
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    
    // Print the list
    printList(head);
    
    return 0;
}

Reverse Linked List (Iterative)

struct Node* reverseList(struct Node* head) {
    struct Node *prev = NULL, *current = head, *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;
    }
    
    return prev;  // New head
}