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
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.