ic/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:T1161,

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:

Calculate the length of the linked list.
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:

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

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)

Code

[{"language":"Java","code":"class Solution {\n    public ListNode binarySearch(ListNode head, int target) {\n        // Step 1: Calculate the length of the linked list\n        int length = 0;\n        ListNode current = head;\n        while (current != null) {\n            length++;\n            current = current.next;\n        }\n\n        // Binary search simulation on linked list\n        int left = 0;\n        int right = length - 1;\n\n        while (left <= right) {\n            // Find the middle node\n            int mid = left + (right - left) / 2;\n            ListNode midNode = getNodeAtIndex(head, mid);\n\n            // Compare the middle node value with the target\n            if (midNode.val == target) {\n                return midNode; // Target found\n            } else if (midNode.val < target) {\n                left = mid + 1; // Move to the right half\n            } else {\n                right = mid - 1; // Move to the left half\n            }\n        }\n\n        return null; // Target not found\n    }\n\n    // Helper function to get the node at a specific index\n    private ListNode getNodeAtIndex(ListNode head, int index) {\n        ListNode current = head;\n        for (int i = 0; i < index; i++) {\n            current = current.next;\n        }\n        return current;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def binarySearch(self, head: ListNode, target: int) -> ListNode:\n        # Step 1: Calculate the length of the linked list\n        len

Related Tags