How to Find the Greatest Common Divisor of Values in a Linked List?

When working with linked lists in coding interviews, a common task is to find the Greatest Common Divisor (GCD) of the values stored within the list nodes. This problem tests your understanding of linked list traversal, mathematical concepts, and efficient implementation. Here’s an easy-to-understand explanation with a clear example to help you prepare.

What is GCD?

The GCD (Greatest Common Divisor) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. For example, GCD of 8 and 12 is 4, because 4 divides both 8 and 12 evenly.

Approach to Find GCD in a Linked List

To find the GCD of all values in a linked list, the idea is straightforward:

1. Initialize a variable to hold the GCD.
2. Traverse the linked list from start to end.
3. At each node, update the GCD of the current GCD and the node's value.
4. After processing all nodes, the value in the GCD variable will be the greatest common divisor of all list elements.

This process makes use of the mathematical property: GCD(a, b, c) = GCD(GCD(a, b), c). It’s enough to repeatedly compute the GCD of the current GCD with the next node value.

Implementation in Python

Below is a simple Python implementation. First, let's define the linked list node:

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next

Next, the function to compute the GCD across the list:

1import math
2
3def gcd_of_linked_list(head):
4    if not head:
5        return 0  # Edge case: empty list
6
7    current_gcd = head.val
8    current_node = head.next
9
10    while current_node:
11        current_gcd = math.gcd(current_gcd, current_node.val)
12        current_node = current_node.next
13    
14    return current_gcd

Example Usage

Suppose we have a linked list with values 24, 36, 48:

1# Create list nodes
2node1 = ListNode(24)
3node2 = ListNode(36)
4node3 = ListNode(48)
5
6# Connect nodes
7node1.next = node2
8node2.next = node3
9
10# Compute GCD
11print(gcd_of_linked_list(node1))  # Output should be 12

This code calculates the GCD of all list node values. The result — 12 — is the largest number that divides 24, 36, and 48 evenly.

Finding the GCD of values in a linked list involves traversing the list once and updating the GCD iteratively. Using Python’s built-in math.gcd() makes the process simple and reliable. This approach has a time complexity of O(n), where n is the number of nodes in the list, making it efficient even for large lists. Practicing this problem will help strengthen your understanding of linked list traversal and basic number theory techniques, useful in many coding interviews.