# 5 Best Ways to Check if Absolute Difference of Consecutive Nodes is 1 in a Linked List in Python

Rate this post

π‘ Problem Formulation: Given a singly linked list, the task is to determine whether the absolute difference between any two consecutive nodes’ values is exactly one. This property must hold true for every pair of adjacent nodes in the list. For example, consider a linked list `4 -> 5 -> 4 -> 3`. The expected outcome of our function would be `True` since the absolute difference between each pair of consecutive nodes is 1.

## Method 1: Iterative Traversal

This method involves an iterative traversal of the linked list. As we iterate, we compare the absolute difference between the value of the current node and that of the next node. If at any point this absolute difference is not equal to one, the function will return `False`. Otherwise, after successfully iterating through the entire list, the function will return `True`.

Here’s an example:

```class Node:
def __init__(self, data=0, next=None):
self.data = data
self.next = next

while current.next:
if abs(current.data - current.next.data) != 1:
return False
current = current.next
return True

node1 = Node(3)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

node1.next = node2
node2.next = node3
node3.next = node4

print(check_consecutive_difference(node1)) # Output should be True
```

The output of this code snippet is `True`.

This code snippet defines a linked list and utilizes a simple iterative approach to traverse it. Function `check_consecutive_difference` checks the absolute difference between consecutive nodes until the end of the list is reached, determining whether it is exactly 1. The main strength of this method is its simplicity and its O(n) time complexity, where n is the number of nodes in the linked list.

## Method 2: Recursive Approach

A recursive approach examines each pair of consecutive nodes by calling the function recursively until the end of the list is reached or until a pair is found that does not meet the criteria. This is an elegant solution that might be clearer to those familiar with recursive functions.

Here’s an example:

```def check_recursive(node):
if not node or not node.next:
return True
return abs(node.data - node.next.data) == 1 and check_recursive(node.next)

# Using the same Nodes defined in Method 1
print(check_recursive(node1)) # Output should be True
```

The output of this code snippet is `True`.

In this recursive code example, function `check_recursive` calls itself for each pair of nodes until a false condition is met or until it reaches the end of the list. The clear advantage is code brevity and readability; however, in practice, recursion might hit the language’s call stack limit if the list is exceptionally long.

## Method 3: Utilizing a Stack

This method involves using a stack data structure to keep track of previous node values as we traverse the list. This potentially can make backtracking simpler if needed, although it is not strictly necessary for our problem.

Here’s an example:

```def check_using_stack(head):
stack = []

while current:
if stack and abs(stack[-1] - current.data) != 1:
return False
stack.append(current.data)
current = current.next

return True

# Using the same Nodes defined in Method 1
print(check_using_stack(node1)) # Output should be True
```

The output of this code snippet is `True`.

In the code, a stack is used to compare each node with the last visited one after pushing it onto the stack. This could be overkill for such a straightforward problem as it introduces additional space complexity O(n). However, where backtracking or more complex operations might be needed, a stack can be very useful.

## Method 4: Using Python’s Higher-Order Functions

This method leverages Python’s higher-order functions, such as `map()` and `zip()`, to create a functional style solution. Although Python does not have a built-in linked list, we can adapt this method to work with custom linked list implementations as well.

Here’s an example:

```# Assuming we have a way to convert our linked list to a Python list for demonstration
linked_list_values = [3, 2, 3, 4]
result = all(diff == 1 for diff in differences)
print(result) # Output should be True
```

The output of this code snippet is `True`.

Our code example here converts the linked list into a Python list (which wouldn’t typically be done in practice) to demonstrate using `map()` with a lambda function checking the absolute differences. The `all()` function then validates all conditions are met. This method provides a concise solution, but converting to a list adds a O(n) space complexity and loses the inherent benefits of using a linked list.

## Bonus One-Liner Method 5: Comprehension with All

A one-liner approach can be achieved by using a Python list comprehension combined with the `all()` function, offering a short and sweet solution. Again, assuming we can operate on a Python list representation of a linked list.

Here’s an example:

```# Assuming a function linked_list_to_list that converts our linked list to a list
print(all(abs(values[i] - values[i+1]) == 1 for i in range(len(values) - 1)))
```

The output for a correctly formatted linked list would be `True`.

This compact approach combines a list comprehension and `all()` to achieve the result in one-line. However, as with Method 4, this assumes the availability of a list representation of the linked list which might not be ideal for all applications.

## Summary/Discussion

• Method 1: Iterative Traversal. Simple and effective with O(n) time complexity. Best suited for straightforward list iteration without additional space requirements.
• Method 2: Recursive Approach. Elegant and readable, but might run into stack overflow issues with very long lists.
• Method 3: Utilizing a Stack. Potentially useful for complex list operations but over-complicates our simple check with unnecessary space complexity.
• Method 4: Python’s Higher-Order Functions. Offers a functional programming approach, but impractical if conversion from linked list to list is required.
• Method 5: Comprehension with All. A concise one-liner but relies on a list representation and misses the linked list’s benefits.