Compare two string linked lists
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Given two singly linked lists where each node stores one character as a string, determine whether the sequences of characters represented by the two lists are identical. Return true if they match exactly, otherwise false.
Quick Answer: This question evaluates proficiency with linked list manipulation and string sequence comparison, focusing on data structure traversal, character-level comparison, and attention to edge cases. It is commonly asked in the Coding & Algorithms domain to assess practical implementation skills, correctness, and efficiency rather than purely conceptual understanding.
You are given two singly linked lists represented as arrays of node values in order. Each node stores exactly one character (a string of length 1). Determine whether the sequences of characters represented by the two lists are identical. Return True if they match exactly (same length and same characters in the same order), otherwise return False.
Constraints
- 0 <= len(list1), len(list2) <= 100000
- Each element in list1 and list2 is a string of length 1
- Characters are case-sensitive
- Aim for O(n) time and O(1) extra space
Solution
from typing import List
def compare_string_linked_lists(list1: List[str], list2: List[str]) -> bool:
# Early exit if lengths differ (arrays represent list lengths)
if len(list1) != len(list2):
return False
# Compare character by character
for i in range(len(list1)):
if list1[i] != list2[i]:
return False
return True
Explanation
Since each node holds a single character and the lists are represented as arrays of values in order, compare corresponding elements in both sequences. If lengths differ or any pair of characters differs, return False; otherwise return True. This avoids building intermediate strings and uses constant extra space.
Time complexity: O(n). Space complexity: O(1).
Hints
- Traverse both sequences in lockstep and compare characters one by one.
- If one sequence ends before the other, they are not identical.
- An early length check (when using arrays) can short-circuit obvious mismatches.