Problem Overview

Given a singly linked list, the task is to return the value of the k-th node from the end of the list. For example, given a list with nodes 1 → 2 → 3 → 4 → 5 and k = 2, the function should return 4, which is the value of the second node from the end. #### Solution 1: Calculate Length and Traverse

This method involves two main steps: 1. Calculate the total length of the linked list by traversing from head to tail. 2. Traverse again from the head node, moving forward (length - k) times to reach the desired node.

Here's the implementation in C: ```

typedef struct ListNode ListNode;

int kthToLast(ListNode* head, int k) { int length = 0; ListNode* current = head;

// Step 1: Calculate the length of the list
while (current != NULL) {
    current = current->next;
    length++;
}

// Step 2: Traverse to the k-th node from the end
current = head;
int steps = length - k;
while (steps-- > 0) {
    current = current->next;
}

return current->val;

}

#### Solution 2: Two Pointers (Fast and Slow)

This approach uses two pointers: fast and slow. The idea is to let the fast pointer move ahead by k steps first. Then, move both pointers simultaneously untill the fast pointer reaches the end of the list. At this point, the slow pointer will be at the k-th node from the end. ```

typedef struct ListNode ListNode;

int kthToLast(ListNode* head, int k) {
    ListNode* fast = head;
    ListNode* slow = head;

    // Move fast pointer ahead by k steps
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }

    // Move both pointers until fast reaches the end
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow->val;
}

Solution 3: Modified Two Pointers Approach

This variation of the two-pointer technique involves moving the fast pointer ahead by only (k - 1) steps instead of k steps. Then, both pointers move together until the fast pointer's next becomes NULL. At this point, the slow pointer will be at the required node. ```

typedef struct ListNode ListNode;

int kthToLast(ListNode* head, int k) { ListNode* fast = head; ListNode* slow = head;

// Move fast pointer ahead by (k - 1) steps
for (int i = 0; i < k - 1; i++) {
    fast = fast->next;
}

// Move both pointers until fast reaches the last node
while (fast->next != NULL) {
    fast = fast->next;
    slow = slow->next;
}

return slow->val;

}