This document covers fundamental linked list operations including element removal, list reversal, node swapping, and intersection detection.

Removing Elements with Specific Value

Approach Without Dummy Node

This implementation handles edge cases by checking the head node separately before processing the rest of the list.

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* temp;
    
    // Handle head nodes that match the target value
    while (head && head->val == val) {
        temp = head;
        head = head->next;
        free(temp);
    }
    
    struct ListNode* curr = head;
    
    // Traverse and remove matching nodes
    while (curr && (temp = curr->next)) {
        if (temp->val == val) {
            curr->next = temp->next;
            free(temp);
        } else {
            curr = curr->next;
        }
    }
    
    return head;
}

Approach With Dummy Node

Using a dummy node simplifies edge case handling by providing a non-null predecessor.

struct ListNode* removeElements(struct ListNode* head, int val) {
    typedef struct ListNode ListNode;
    
    // Create dummy node
    ListNode* dummy;
    dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;
    
    ListNode* curr = dummy;
    
    // Iterate through list
    while (curr->next != NULL) {
        if (curr->next->val == val) {
            ListNode* toDelete = curr->next;
            curr->next = curr->next->next;
            free(toDelete);
        } else {
            curr = curr->next;
        }
    }
    
    head = dummy->next;
    free(dummy);
    
    return head;
}

Linked List Class Implementation

A complete linked list implementation supporting basic operations.

typedef struct MyLinkedList {
    int val;
    struct MyLinkedList* next;
} MyLinkedList;

MyLinkedList* myLinkedListCreate() {
    MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    head->next = NULL;
    return head;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    MyLinkedList* cur = obj->next;
    for (int i = 0; cur != NULL; i++) {
        if (i == index) {
            return cur->val;
        }
        cur = cur->next;
    }
    return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList* newNode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newNode->val = val;
    newNode->next = obj->next;
    obj->next = newNode;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList* cur = obj;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    MyLinkedList* newNode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newNode->val = val;
    newNode->next = NULL;
    cur->next = newNode;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if (index == 0) {
        myLinkedListAddAtHead(obj, val);
        return;
    }
    MyLinkedList* cur = obj->next;
    for (int i = 1; cur != NULL; i++) {
        if (i == index) {
            MyLinkedList* newNode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
            newNode->val = val;
            newNode->next = cur->next;
            cur->next = newNode;
            return;
        }
        cur = cur->next;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if (index == 0) {
        MyLinkedList* toDelete = obj->next;
        if (toDelete != NULL) {
            obj->next = toDelete->next;
            free(toDelete);
        }
        return;
    }
    MyLinkedList* cur = obj->next;
    for (int i = 1; cur != NULL && cur->next != NULL; i++) {
        if (i == index) {
            MyLinkedList* toDelete = cur->next;
            if (toDelete != NULL) {
                cur->next = toDelete->next;
                free(toDelete);
            }
            return;
        }
        cur = cur->next;
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    while (obj != NULL) {
        MyLinkedList* tmp = obj;
        obj = obj->next;
        free(tmp);
    }
}

Reversing a Linked List

Two-Pointer Iteration

This method uses the head insertion technique to reverse the list in place.

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* temp;
    struct ListNode* prev = NULL;
    
    while (head) {
        temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    
    return prev;
}

Recursive Approach

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

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* reverseRecursive(struct ListNode* prev, struct ListNode* curr) {
    if (!curr)
        return prev;
    
    struct ListNode* next = curr->next;
    curr->next = prev;
    
    return reverseRecursive(curr, next);
}

struct ListNode* reverseList(struct ListNode* head) {
    return reverseRecursive(NULL, head);
}

int main() {
    // Example usage
    struct ListNode* head = malloc(sizeof(struct ListNode));
    struct ListNode* n1 = malloc(sizeof(struct ListNode));
    struct ListNode* n2 = malloc(sizeof(struct ListNode));
    struct ListNode* n3 = malloc(sizeof(struct ListNode));
    struct ListNode* n4 = malloc(sizeof(struct ListNode));
    
    head->val = 1;
    head->next = n1;
    n1->val = 2;
    n1->next = n2;
    n2->val = 3;
    n2->next = n3;
    n3->val = 4;
    n3->next = n4;
    n4->val = 5;
    n4->next = NULL;
    
    struct ListNode* reversed = reverseList(head);
    
    // Print reversed list
    struct ListNode* current = reversed;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    
    // Cleanup
    while (reversed != NULL) {
        struct ListNode* tmp = reversed;
        reversed = reversed->next;
        free(tmp);
    }
    
    return 0;
}

Swapping Adjacent Node Pairs

Recursive Solution

struct ListNode* swapPairs(struct ListNode* head) {
    if (!head || !head->next)
        return head;
    
    struct ListNode* newHead = head->next;
    head->next = swapPairs(newHead->next);
    newHead->next = head;
    
    return newHead;
}

Iterative Solution

struct ListNode* swapPairs(struct ListNode* head) {
    typedef struct ListNode ListNode;
    
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;
    
    ListNode* right = dummy->next;
    ListNode* left = dummy;
    
    while (left && right && right->next) {
        left->next = right->next;
        right->next = left->next->next;
        left->next->next = right;
        
        left = right;
        right = left->next;
    }
    
    return dummy->next;
}

Removing Nth Node From End

This uses the fast-slow pointer technique to locate and remove the nth node from the end.

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    
    struct ListNode* fast = head;
    struct ListNode* slow = dummy;
    
    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    slow->next = slow->next->next;
    head = dummy->next;
    free(dummy);
    
    return head;
}

The algorithm proceeds as follows:

1. Initialize fast and slow pointers with slow at dummy
2. Advance fast by n+1 positions to create the required gap
3. Move both pointers until fast reaches the end
4. Remove the node after slow

Finding List Intersection

The intersection point is where two lists share the same node object, not just the same value.

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

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* longer = NULL;
    struct ListNode* shorter = NULL;
    int lenA = 0, lenB = 0, gap = 0;
    
    // Calculate length of list A
    shorter = headA;
    while (shorter) {
        lenA++;
        shorter = shorter->next;
    }
    
    // Calculate length of list B
    shorter = headB;
    while (shorter) {
        lenB++;
        shorter = shorter->next;
    }
    
    // Determine longer and shorter lists
    if (lenA > lenB) {
        longer = headA;
        shorter = headB;
        gap = lenA - lenB;
    } else {
        longer = headB;
        shorter = headA;
        gap = lenB - lenA;
    }
    
    // Align both lists
    while (gap--) {
        longer = longer->next;
    }
    
    // Find intersection
    while (longer) {
        if (longer == shorter) {
            return longer;
        }
        longer = longer->next;
        shorter = shorter->next;
    }
    
    return NULL;
}

int main() {
    // Build test lists with intersection
    struct ListNode* common = (struct ListNode*)malloc(sizeof(struct ListNode));
    common->val = 8;
    common->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    common->next->val = 4;
    common->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    common->next->next->val = 5;
    common->next->next->next = NULL;
    
    struct ListNode* headA = (struct ListNode*)malloc(sizeof(struct ListNode));
    headA->val = 4;
    headA->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    headA->next->val = 1;
    headA->next->next = common;
    
    struct ListNode* headB = (struct ListNode*)malloc(sizeof(struct ListNode));
    headB->val = 5;
    headB->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    headB->next->val = 6;
    headB->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    headB->next->next->val = 1;
    headB->next->next->next = common;
    
    struct ListNode* result = getIntersectionNode(headA, headB);
    
    if (result) {
        printf("Intersection value: %d\n", result->val);
    } else {
        printf("No intersection\n");
    }
    
    free(headA);
    free(headB);
    free(common);
    
    return 0;
}

Key steps:

1. Calculate lengths of both lists
2. Align the longer list by advancing it by the length difference
3. Traverse both lists simultaneously until node pointers match