Check if Absolute Difference of Consecutive Nodes is 1 in a Linked List

Table of Contents#

1. Introduction
2. What is a Linked List?
3. Problem Statement
4. Approach to Solve the Problem
5. Implementation Steps
6. Example Walkthrough
7. Edge Cases
8. Best Practices
9. Common Pitfalls
10. Conclusion
11. References

What is a Linked List?#

A linked list is a linear data structure consisting of nodes, where each node contains:

• Data: The value stored in the node.
• Next Pointer: A reference (or pointer) to the next node in the sequence.

Unlike arrays, linked lists do not require contiguous memory; nodes are scattered in memory, connected via pointers. The simplest type is a singly linked list, where each node points only to the next node.

Example Node Structure (Python):#

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # Data stored in the node
        self.next = next  # Reference to the next node

Example Linked List:#

A linked list 1 -> 2 -> 3 -> 4 is represented as:
ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Problem Statement#

Given a singly linked list, determine if the absolute difference between the values of every pair of consecutive nodes is exactly 1.

Formal Definition:

• Let the linked list be head -> n1 -> n2 -> ... -> nk, where n1, n2, ..., nk are nodes.
• For all i from 1 to k-1, check if |n_i.val - n_{i+1}.val| == 1.
• Return True if all consecutive pairs satisfy this condition; otherwise, return False.

Approach to Solve the Problem#

The problem can be solved with a linear traversal of the linked list. Here’s the high-level approach:

1. Traverse the linked list starting from the head node.
2. For each node, compare its value with the value of the next node.
3. Compute the absolute difference between the two values.
4. If any pair of consecutive nodes has an absolute difference not equal to 1, return False.
5. If all consecutive pairs pass the check, return True.

Key Observations:#

• Time Complexity: O(n), where n is the number of nodes. We traverse the list once.
• Space Complexity: O(1), as we only use a constant amount of extra space (a pointer to track the current node).

Implementation Steps#

Let’s outline the steps to implement the solution:

Step 1: Handle Edge Cases#

• If the list is empty (head is None) or has only one node, return True (no consecutive pairs to check).

Step 2: Traverse the List#

• Initialize a pointer current to head.
• While current and current.next are not None (i.e., there is a next node to compare):
  • Compute the absolute difference between current.val and current.next.val.
  • If the difference is not 1, return False.
  • Move current to current.next to check the next pair.

Step 3: Return True#

• If the loop completes without finding any invalid pairs, return True.

Example Walkthrough#

Let’s walk through two examples to illustrate the solution.

Example 1: Valid Linked List#

Input: 1 -> 2 -> 3 -> 4

• Traversal:
  • current = 1, current.next = 2: |1 - 2| = 1 → valid.
  • current = 2, current.next = 3: |2 - 3| = 1 → valid.
  • current = 3, current.next = 4: |3 - 4| = 1 → valid.
• Result: True.

Example 2: Invalid Linked List#

Input: 1 -> 3 -> 2

• Traversal:
  • current = 1, current.next = 3: |1 - 3| = 2 → invalid.
• Result: False.

Edge Cases#

It’s critical to test edge cases to ensure robustness:

1. Empty List: head = None → Return True (no pairs to check).
2. Single Node: head = ListNode(5) → Return True (no consecutive pairs).
3. Two Nodes with Difference 1: 5 -> 6 → Return True.
4. Two Nodes with Difference ≠ 1: 5 -> 7 → Return False.
5. Negative Values: -1 -> 0 -> 1 → |-1 - 0| = 1, |0 - 1| = 1 → Return True.
6. Mixed Positive/Negative: 2 -> 1 -> 0 -> -1 → |2-1|=1, |1-0|=1, |0 - (-1)|=1 → Return True.

Best Practices#

To write clean, efficient, and maintainable code:

1. Handle Null Pointers: Always check if current.next exists before accessing it to avoid NullReferenceError (or AttributeError in Python).
2. Use Absolute Difference: Explicitly use abs() to ensure the difference is non-negative (e.g., |a - b| instead of a - b).
3. Efficient Traversal: Traverse the list once (O(n) time) with O(1) space—avoid unnecessary copies or recursion.
4. Clear Variable Names: Use descriptive names like current instead of temp to improve readability.
5. Test Edge Cases: Include tests for empty lists, single nodes, and negative values.

Common Pitfalls#

Avoid these mistakes when implementing the solution:

1. Forgetting to Check current.next: Accessing current.next.val when current.next is None causes a crash. Always check current.next exists before comparing.
2. Miscalculating the Difference: Omitting abs() (e.g., checking current.val - current.next.val == 1 instead of abs(...) == 1) will fail for decreasing sequences (e.g., 3 -> 2).
3. Returning False for Empty/Single-Node Lists: These cases should return True since there are no invalid pairs.
4. Overcomplicating the Logic: Recursion or extra data structures (e.g., arrays) are unnecessary here—linear traversal is optimal.

Implementation Code#

Python#

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def has_consecutive_difference(head: ListNode) -> bool:
    # Edge case: empty list or single node
    if not head or not head.next:
        return True
    
    current = head
    while current.next:
        # Compute absolute difference
        diff = abs(current.val - current.next.val)
        if diff != 1:
            return False
        current = current.next  # Move to next node
    
    return True

Java#

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
 
public class Solution {
    public boolean hasConsecutiveDifference(ListNode head) {
        // Edge case: empty list or single node
        if (head == null || head.next == null) {
            return true;
        }
        
        ListNode current = head;
        while (current.next != null) {
            int diff = Math.abs(current.val - current.next.val);
            if (diff != 1) {
                return false;
            }
            current = current.next;
        }
        
        return true;
    }
}

Conclusion#

Checking if consecutive nodes in a linked list have an absolute difference of 1 is a classic problem that tests understanding of linked list traversal and edge-case handling. By following a linear traversal approach and adhering to best practices (e.g., null checks, absolute difference), you can efficiently solve this problem in O(n) time with O(1) space.

This problem is not only useful for validating sequences but also reinforces core linked list operations, making it a staple in coding interviews and algorithmic problem-solving.

References#

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• GeeksforGeeks. "Check if linked list is sorted in ascending order." Link
• LeetCode Problem: "Linked List Cycle" (related linked list traversal practice). Link