Problem

Given the head of a linked list, determine whether the length of the list is even or odd.

Examples

Example 1:

1
2

Input: head = [1, 2, 3, 4, 5]
Output: The length of the linked list is odd.

Example 2:

1
2

Input: head = [1, 2, 3, 4]
Output: The length of the linked list is even.

Solution

Method 1 - Slow and Fast Pointers

Use a 2x pointer( two nodes at a time). Take a pointer that moves at 2x. At the end, if the length is even, then the pointer will be NULL; otherwise it will point to the last node.

To solve this problem, we can use a fast pointer approach:

  1. Fast Pointer Traversal: Move the fast pointer two nodes at a time while checking if it reaches the end.
  2. Determine Length Parity:
    • If the fast pointer reaches the end (null), the length is even.
    • If the fast pointer reaches a node and its next node is null, the length is odd.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class Solution {
    public boolean isLengthEven(ListNode head) {
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
        }

        return fast == null;
    }
}
1
2
3
4
5
6

class Solution:
    def isLengthEven(self, head: ListNode) -> bool:
        fast = head
        while fast and fast.next:
            fast = fast.next.next
        return fast is None

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. The list is traversed once.
  • 🧺 Space complexity: O(1), since only a constant amount of extra space is used for the pointer.