Deleting Nodes by Value in a Linked List

A direct approach is to construct a new list containing only the nodes whoce values differ from the target. Traverse the original list, and when a node with a non-matching value is found, append it to the result. Care must be taken to terminate the new list properly.

typedef struct ListNode ListNode;

struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode *resultHead = NULL, *resultTail = NULL;
    ListNode *cursor = head;

    while (cursor) {
        if (cursor->val != val) {
            if (resultHead == NULL) {
                resultHead = resultTail = cursor;
            } else {
                resultTail->next = cursor;
                resultTail = cursor;
            }
        }
        cursor = cursor->next;
    }

    if (resultTail) {
        resultTail->next = NULL;
    }
    return resultHead;
}

In-Place Reversal of a Linked List

The pointer direction of each node is reversed so that the tail becomes the new head. Three cursors track the previous, current, and next nodes as the iteration porgresses.

typedef struct ListNode ListNode;

struct ListNode* reverseList(struct ListNode* head) {
    if (!head) return head;

    ListNode *prev = NULL, *curr = head, *next = curr->next;

    while (curr) {
        curr->next = prev;
        prev = curr;
        curr = next;
        if (next) {
            next = next->next;
        }
    }

    return prev;
}

Merging Two Sorted Lists

A dummy head simplifies the merging logic. The two input lists are compared element by element, and the smaller node is attached to the merged list. After one list is exhausted, the remaining node are linked directly.

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    ListNode dummy;
    ListNode *tail = &dummy;
    dummy.next = NULL;

    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    tail->next = list1 ? list1 : list2;
    return dummy.next;
}

Checking Palindromic Structure in a Linked List

A palindrome list reads identically forwards and backwards. By locating the midpoint with fast and slow pointers and reversing the second half, we can compare the halves directly. If any corresponding values mismatch, the list is not a palindrome.

typedef struct ListNode ListNode;

class PalindromeList {
public:
    ListNode* findMiddle(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode* reverseSegment(ListNode* head) {
        ListNode *prev = NULL, *curr = head, *next = NULL;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    bool chkPalindrome(ListNode* A) {
        if (!A) return true;
        ListNode* mid = findMiddle(A);
        ListNode* rightReversed = reverseSegment(mid);
        ListNode* left = A;

        while (rightReversed) {
            if (left->val != rightReversed->val)
                return false;
            left = left->next;
            rightReversed = rightReversed->next;
        }
        return true;
    }
};