mediumLinked ListPattern: Two Pointers
Find First Node With Specific Offset Solution
Problem Statement
Given the head of a singly linked list, where each node contains a unique integer value, find the first pair of nodes (node A, node B) such that node B appears exactly 27 positions after node A in the list. Return the values of node A and node B as a pair. If no such pair exists, return an empty pair or a specific indicator (e.g., `[-1, -1]`).
Examples
Example 1:
Input:1 -> 2 -> 3 -> ... -> 27 -> 28 -> 29 -> ...
Output:[-1,-1]
Explanation: The first node has value 1. The node 27 positions after it is the node with value 28. Thus, the pair is [1, 28].
Example 2:
Input:5 -> 10 -> 15 -> ... -> (5 + 26*5) -> (5 + 27*5) -> ...
Output:[-1,-1]
Explanation: The first node has value 5. The node 27 positions after it has value 5 + 27 * 5 = 140. Thus, the pair is [5, 140].
Example 3:
Input:1 -> 2 -> ... -> 26
Output:[-1, -1]
Explanation: The list has only 26 nodes. It's impossible to find a node that is 27 positions after another node. Thus, return [-1, -1].
Constraints
- The number of nodes in the list is between 0 and 10^5.
- Node values are unique integers.
- The offset (27) is a fixed positive integer.
- Node values can range from -10^9 to 10^9.
Time: O(N) Space: O(1)
Use the two-pointer technique. Initialize a 'fast' pointer and a 'slow' pointer to the head of the list. Advance the 'fast' pointer 27 steps. If the 'fast' pointer reaches the end (null) before completing 27 steps, no such pair exists. Then, advance both 'fast' and 'slow' pointers one step at a time until the 'fast' pointer reaches the end of the list. The 'slow' pointer will then be pointing to the first node of the required pair.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_first_node_with_specific_offset(head):
if not head:
return [-1, -1]
current_node = head
offset = 27
while current_node:
lookahead_node = current_node
steps = 0
# Try to advance 'offset' steps from current_node
while steps < offset and lookahead_node:
lookahead_node = lookahead_node.next
steps += 1
# If we successfully advanced 'offset' steps and lookahead_node is valid
if steps == offset and lookahead_node:
return [current_node.val, lookahead_node.val]
# Move to the next node to check
current_node = current_node.next
# If no such pair is found
return [-1, -1]