K-th Node from the End of a Linked List

1. Problem Description

Given a linked list, return its k-th node from the end.

2. Approach

• Traverse and store nodes in an array, then take the len-k element
• Traverse once to get the total length; the k-th node from the end corresponds to position len-k from the front
• Fast-slow pointers: advance fast by k steps, then move fast and slow together until fast is nil

3. Implementation

3.1. Array

• java

public class 链表中倒数第k个结点
{
    public ListNode FindKthToTail(ListNode head, int k)
    {
        // Check parameters
        if (head == null || k <= 0)
        {
            return null;
        }

        // Put all nodes into a list
        LinkedList<ListNode> list = new LinkedList<>();
        ListNode current = head;
        while (current != null)
        {
            list.add(current);
            current = current.next;
        }

        // Check the length
        if (list.size() < k)
        {
            return null;
        }

        // For 4->5->6, the second node from the end corresponds to list.size-2
        return list.get(list.size() - k);
    }
}

• go

// Traverse and store nodes in an array, then take the len-k element
// Time: O(n)
// Space: O(n)
func FindKthToTail(pListHead *ListNode, k int) *ListNode {
	if pListHead == nil || k <= 0 {
		return nil
	}

	vals := make([]*ListNode, 0)
	node := pListHead
	for node != nil {
		vals = append(vals, node)
		node = node.Next
	}

	if len(vals) < k {
		return nil
	}

	return vals[len(vals) - k]
}

3.2. Convert from End Position to Forward Position

// Traverse once to get the total length; the k-th node from the end corresponds to position len-k from the front
// Time: O(n)
// Space: O(1)
func FindKthToTail2(pListHead *ListNode, k int) *ListNode {
	if pListHead == nil || k <= 0 {
		return nil
	}

	count := 0
	n := pListHead
	for n != nil {
		count++
		n = n.Next
	}

	if count<k {
		return nil
	}

	n = pListHead
	for i := 0; i < count-k; i++ {
		n = n.Next
	}

	return n
}

3.3. Two Pointers

• java

 public ListNode FindKthToTail(ListNode head, int k)
    {
        // Check parameters
        if (head == null || k <= 0)
        {
            return null;
        }

        // For 4->5->6->7->8, find the second node from the end
        //         P1 P2
        
        // Use two pointers; advance the first pointer first and make sure the list is long enough
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k; i++)
        {
            if (fast == null)
            {
                return null;
            }
            fast = fast.next;

        }
        // Move both pointers together; when the first reaches the end, return the second
        while (fast != null)
        {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

• go

// Fast-slow pointers: advance fast by k steps, then move both until fast becomes nil
// Time: O(n)
// Space: O(1)
func FindKthToTail3(pListHead *ListNode, k int) *ListNode {
	if pListHead == nil || k <= 0 {
		return nil
	}

	fast := pListHead
	slow := pListHead
	for i := 0; i < k; i++ {
		if fast == nil {
			return nil
		}
		fast = fast.Next
	}

	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	return slow
}

4. References

• K-th Node from the End of a Linked List - NowCoder
• Interview Question 02.02. K-th Node from the End - LeetCode