Problem

Given the head of a sorted singly linked list and a target value, implement a function to find the target value using a binary search approach. If the target is found in the linked list, return the node; otherwise, return None.

Examples

Example 1:

 Input: head = [1, 3, 5, 7, 9, 11], target = 7
 Output: Node with value 7
 Explanation: The target 7 is found in the linked list.

Example 2:

 Input: head = [1, 3, 5, 7, 9, 11], target = 4
 Output: None
 Explanation: The target 4 is not found in the linked list.

Solution

Method 1 - Binary Search

The key steps involve:

  1. Calculate the length of the linked list.
  2. Simulate the binary search using the length to cut the list in halves iteratively.

Here are the steps to perform binary search on a linked list:

  1. Calculate the length of the linked list.
  2. Use the length to simulate the binary search by finding the middle element in each iteration.
  3. Compare the target with the middle element and adjust the search range accordingly.

Code

Java
class Solution {
    public ListNode binarySearch(ListNode head, int target) {
        // Step 1: Calculate the length of the linked list
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // Binary search simulation on linked list
        int left = 0;
        int right = length - 1;

        while (left <= right) {
            // Find the middle node
            int mid = left + (right - left) / 2;
            ListNode midNode = getNodeAtIndex(head, mid);

            // Compare the middle node value with the target
            if (midNode.val == target) {
                return midNode; // Target found
            } else if (midNode.val < target) {
                left = mid + 1; // Move to the right half
            } else {
                right = mid - 1; // Move to the left half
            }
        }

        return null; // Target not found
    }

    // Helper function to get the node at a specific index
    private ListNode getNodeAtIndex(ListNode head, int index) {
        ListNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }
}
Python
class Solution:
    def binarySearch(self, head: ListNode, target: int) -> ListNode:
        # Step 1: Calculate the length of the linked list
        length = 0
        current = head
        while current:
            length += 1
            current = current.next

        # Binary search simulation on the linked list
        left = 0
        right = length - 1

        while left <= right:
            # Find the middle node
            mid = left + (right - left) // 2
            midNode = self.getNodeAtIndex(head, mid)

            # Compare the middle node value with the target
            if midNode.val == target:
                return midNode  # Target found
            elif midNode.val < target:
                left = mid + 1  # Move to the right half
            else:
                right = mid - 1  # Move to the left half

        return None  # Target not found

    # Helper function to get the node at a specific index
    def getNodeAtIndex(self, head: ListNode, index: int) -> ListNode:
        current = head
        for _ in range(index):
            current = current.next
        return current

Complexity

  • ⏰ Time complexity: O(n log n)
    • The approach is not as efficient as binary search on an array because each getNodeAtIndex call may require traversing up to half the length of the linked list.
    • The time complexity for each getNodeAtIndex call is O(n), making the overall complexity approximately O(n log n).
  • 🧺 Space complexity: O(1)