Teaching Kids Programming – Compute the Kth Last Node of a Linked List (and Length of a Linked List)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Linked List, find out which is the Kth Node from the end of the Linked List. For example 1-2-3-4-5, the second last node is 4.

Implement an algorithm to find the kth to last element of a singly linked list. Return the value of the element.

Example:
Input: 1->2->3->4->5 and k = 2
Output: 4
Note:
k is always valid.

Find the Length of a Linked List

We can find the length of the linked list, this will take O(N) time (one pass), then we know which node we want (L – k), and the second pass will help us retrive the K-th Node from the last.

To compute the length of a linked list, we can do this recursively:

1
2
3
4

def getLength(head):
   if head is None:
     return 0
   return 1 + getLength(head.next)

def getLength(head):
   if head is None:
     return 0
   return 1 + getLength(head.next)

Alternatively, we can do this iteratively.

1
2
3
4
5
6

def getLength(head):
   ans = 0
   while head:
      ans += 1
      head = head.next
   return ans

def getLength(head):
   ans = 0
   while head:
      ans += 1
      head = head.next
   return ans

Two Pointer to Compute the K-th Last Node

We can let the first pointer walk K step, and then the second pointer starts. The distance between two pointers will be K. Therefore when first pointer reaches the end (Null), the second pointer will be exactly Kth Node from the last.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        p = head
        for i in range(k):
            p = p.next
        while p:
            p = p.next
            head = head.next
        return head.val

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        p = head
        for i in range(k):
            p = p.next
        while p:
            p = p.next
            head = head.next
        return head.val

Both implementations run at time complexity O(N) where N is the number of the nodes in the linked list.

Length of a Linked List Algorithm

• Algorithms to Compute the Length of a Linked List
• Teaching Kids Programming – Compute the Kth Last Node of a Linked List (and Length of a Linked List)
• Teaching Kisd Programming – Finding the Length of a Linked List (Recursion and Iterative Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —