Finding the Kth Node from the End of a Linked List

To locate the kth node from the end efficient, use two pointers—fast and slow. Advance the fast pointer by k steps first. Then move both pointers forward until fast reaches the end. At this point, slow will be pointing to the desired node.

int kthToLast(struct ListNode* head, int k) {
    struct ListNode *slow = head, *fast = head;
    
    for (int i = 0; i < k; ++i) {
        fast = fast->next;
    }
    
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow->val;
}

Checking if a Linked List is a Palindrome

A palindrome reads the same forwards and backwards. To verify this structure:

1. Use fast and slow pointers to find the middle of the list.
2. Reverse the second half starting from the middle.
3. Compare nodes from the original head and the reversed second half.

If all corresponding values match during traversal, the list is a pailndrome.

class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Reverse second half
        ListNode *prev = nullptr, *curr = slow;
        while (curr) {
            ListNode *nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // Compare first half with reversed second half
        ListNode *left = head, *right = prev;
        while (right) {
            if (left->val != right->val) return false;
            left = left->next;
            right = right->next;
        }
        
        return true;
    }
};

Detecting the Intersection Node of Two Linked Lists

Two singly linked lists intersect if they share a common tail. First, travrese both lists to compare their tail nodes—if different, no intersection exists.

If they do intersect:

1. Compute lengths of both lists.
2. Align the starting points by advancing the pointer of the longer list by the difference in lengths.
3. Traverse both lists in tandem until the shared node is found.

Node comparison must be based on memory addresses, not values, to avoid false positives.

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (!headA || !headB) return NULL;
    
    struct ListNode *tailA = headA, *tailB = headB;
    int lenA = 1, lenB = 1;
    
    while (tailA->next) { tailA = tailA->next; lenA++; }
    while (tailB->next) { tailB = tailB->next; lenB++; }
    
    if (tailA != tailB) return NULL;
    
    struct ListNode *longer = (lenA > lenB) ? headA : headB;
    struct ListNode *shorter = (lenA > lenB) ? headB : headA;
    int diff = abs(lenA - lenB);
    
    for (int i = 0; i < diff; ++i) {
        longer = longer->next;
    }
    
    while (longer != shorter) {
        longer = longer->next;
        shorter = shorter->next;
    }
    
    return longer;
}