Finding the Kth Node from the End of a Singly Linked List: Two-Pointer Gap Method

Table of Contents

Problem Description Solution Approach The Problem with the Brute Force Method Two-Pointer Gap Method (Single Traversal)Algorithm Steps Key Detail: Where Should fast Stop?Code Implementation Illustrated Walkthrough Complexity Analysis Key Takeaways Extended Thinking

805 words

4 minutes

Finding the Kth Node from the End of a Singly Linked List: Two-Pointer Gap Method

2026-08-10

Algorithms

Linked List

/

Two Pointers

/

Sliding Window

/

C

/

C++

/

JavaScript

Problem Description#

Given the head node head of a singly linked list and a positive integer k, return the kth from the end node in the linked list.

1
Input: head = 1→2→3→4→5, k = 2
2
Output: 4→5
3
Explanation: The 2nd node from the end is 4

Solution Approach#

The Problem with the Brute Force Method#

The most straightforward idea is to first traverse the list to find its length n, then walk n - k steps from the beginning. But this requires two traversals.

Two-Pointer Gap Method (Single Traversal)#

Imagine two people racing on a straight road: A runs K meters ahead first, then B starts running. When A reaches the finish line, B is exactly K meters from the finish line—which is the “Kth from the end” position.

Applied to a linked list:

The fast pointer moves k steps first
Then slow and fast advance in sync (each moving one step at a time)
When fast reaches null (the end), slow points exactly to the kth from the end node

Algorithm Steps#

The fast pointer moves k steps first
If fast becomes null while moving k steps → k exceeds the list length, return null
slow and fast advance in sync until fast points to null
Return slow (at this point slow points to the kth from the end node)

Key Detail: Where Should fast Stop?#

Assume the list length is n, and the kth from the end node is the n - kth node from the start (1-indexed).

fast moves k steps first, reaching the (k+1)th node
slow starts from the 1st node
When fast reaches the (n+1)th position (null), slow advances in sync to the (n+1) - k = n - k + 1th node
This is exactly the kth from the end ✓

Code Implementation#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
ListNode* findKthFromEnd(ListNode* head, int k) {
10
    ListNode *fast = head;
11
    ListNode *slow = head;
12

13
    // fast moves k steps first
14
    for (int i = 0; i < k; i++) {
15
        // k exceeds the linked list length
16
        if (!fast) return NULL;
17
        fast = fast->next;
18
    }
19

20
    // slow and fast advance in sync
21
    while (fast) {
22
        slow = slow->next;
23
        fast = fast->next;
24
    }
25

26
    // when fast reaches null, slow points to the k-th node from the end
27
    return slow;
28
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode() : val(0), next(nullptr) {}
5
    ListNode(int x) : val(x), next(nullptr) {}
6
    ListNode(int x, ListNode *next) : val(x), next(next) {}
7
};
8

9
class Solution {
10
public:
11
    ListNode* findKthFromEnd(ListNode* head, int k) {
12
        ListNode *fast = head;
13
        ListNode *slow = head;
14

15
        // fast moves k steps first
16
        for (int i = 0; i < k; i++) {
17
            // k exceeds the linked list length
18
            if (!fast) return nullptr;
19
            fast = fast->next;
20
        }
21

22
        // slow and fast advance in sync
23
        while (fast) {
24
            slow = slow->next;
25
            fast = fast->next;
26
        }
27

28
        // when fast reaches null, slow points to the k-th node from the end
29
        return slow;
30
    }
31
};

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
function findKthFromEnd(head, k) {
9
    let fast = head;
10
    let slow = head;
11

12
    // fast moves k steps first
13
    for (let i = 0; i < k; i++) {
14
        // k exceeds the linked list length
15
        if (!fast) return null;
16
        fast = fast.next;
17
    }
18

19
    // slow and fast advance in sync
20
    while (fast) {
21
        slow = slow.next;
22
        fast = fast.next;
23
    }
24

25
    // when fast reaches null, slow points to the k-th node from the end
26
    return slow;
27
}

Illustrated Walkthrough#

1
Input: head = 1→2→3→4→5, k = 2
2

3
Initial: fast and slow are both at the head node
4
        fast
5
        slow
6
        ↓
7
        1 → 2 → 3 → 4 → 5
8

9
Step 1: fast moves k=2 steps first
10
                     fast
11
                     ↓
12
        1 → 2 → 3 → 4 → 5
13
        ↑
14
        slow
15

16
Step 2: slow and fast move in sync
17
                     fast
18
                     ↓
19
        1 → 2 → 3 → 4 → 5 → null
20
                  ↑
21
                  slow
22

23
When fast == null, slow points to node 4 (the 2nd node from the end)

Complexity Analysis#

Dimension	Analysis
Time Complexity	O(n) — only one traversal of the list
Space Complexity	O(1) — only two pointers used

Key Takeaways#

The gap concept: fast and slow always maintain a gap of k steps—this is the core of the two-pointer technique
Boundary handling: while fast moves k steps first, if it becomes null midway, it means k > n, and null should be returned
Single traversal: compared to the two-traversal approach of “find length first, then walk n-k steps,” two pointers need only one

Extended Thinking#

If you need to delete the kth from the end node (LeetCode 19), how can you use this problem’s approach to find the (k+1)th from the end node?
If the list is doubly linked, is there a more optimal solution?