Algorithms to Compute the Kth Last Node of a Linked List

Given a singly linked list node, return the value of the kth last node (0-indexed). k is guaranteed not to be larger than the size of the linked list. For example, given 10 – 20 – 30 – 40 – 50, and k = 1, return 40.

The linked list has the fields next and val.
Constraints
n ≤ 100,000 where n is the length of node

Example 1
Input
node = 1 → 2
k = 1
Output
1
Explanation
The second last node has the val of 1

Example 2
Input
node = 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
k = 2
Output
7
Explanation
Last node (index 0) has val of 9
Second last node (index 1) has val of 8
Third last node (index 2) has val of 7

Two Passes Algorithm to Compute the Kth Last Node of a Linked List

We can compute the total length of the linked list N and then follow the path for the (N-K)th node from the begining. This algorithm requires two passes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int solve(LLNode* node, int k) {
    LLNode* fast = node;
    int n = 0;
    while (fast) {
        n ++;
        fast = fast->next;
    }
    LLNode* slow = node;
    for (int i = 1; i < n - k; ++ i) {
        slow = slow->next;
    }
    return slow->val;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int solve(LLNode* node, int k) {
    LLNode* fast = node;
    int n = 0;
    while (fast) {
        n ++;
        fast = fast->next;
    }
    LLNode* slow = node;
    for (int i = 1; i < n - k; ++ i) {
        slow = slow->next;
    }
    return slow->val;
}

One Pass Algorithm to Retreive the Kth Last Node of a Linked List

We can first walk K steps along the linked list from the root (first node), and then we spawn another walker from the begining and these two nodes should have K nodes away. They both walk one step at a time and when the first node reaches the end, the second node is the K-th last node of the linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int solve(LLNode* node, int k) {
    LLNode *first = node;
    while (first && (k--)) {
        first = first->next;
    }
    LLNode *second = node;
    while (first->next) {
        first = first->next;
        second = second->next;
    }
    return second->val;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int solve(LLNode* node, int k) {
    LLNode *first = node;
    while (first && (k--)) {
        first = first->next;
    }
    LLNode *second = node;
    while (first->next) {
        first = first->next;
        second = second->next;
    }
    return second->val;
}

Both implementations are O(N) time and O(1) space. However, the second approach is twice faster because it only scans the linked list once (one pass).

–EOF (The Ultimate Computing & Technology Blog) —