Easy difficulty · Algorithm · Topics: linked-list, two-pointers, comparison
Compare two linked lists node by node and return -1 if the first is smaller, 0 if they are equal and 1 if the first is larger, using lexicographic (dictionary) order. The same walk answers the plain equality question: two lists are equal exactly when the result is 0. The lists are passed as arrays and built into nodes inside the function.
Comparing two words: look at the first letters; if they differ, that decides it. If they match, move to the second letters, and so on. If one word runs out while the other still has letters, the shorter word comes first ("car" < "card"). Linked lists work the same way, with one pointer walking each list in lock-step.
Because a linked list has no length field and no random access, you cannot jump to the end or compare sizes cheaply. The synchronized walk is therefore the natural algorithm: it finds the first position where the lists differ, or discovers that one list ends first.
curr1 on the head of the first list and curr2 on the head of the second.curr1.val < curr2.val: return .-1curr1.val > curr2.val: return 1.null:
null: same length and every value matched, return 0 (equal);curr1 is null: the first list is a prefix of the second, return -1;curr2 is null: return 1.Test case 0: list1 = 1 -> 2 -> 3, list2 = 1 -> 2 -> 4.
| Step | curr1.val | curr2.val | Decision |
|---|---|---|---|
| 1 | 1 | 1 | equal, advance both |
| 2 | 2 | 2 | equal, advance both |
| 3 | 3 | 4 | 3 < 4, return -1 |
Other cases: [1, 2, 3] vs [1, 2, 3] runs out of nodes together and returns 0; [1, 2] vs [1, 2, 3] ends with curr1 === null and returns -1.
| Measure | Cost | Why |
|---|---|---|
| Time | O(min(n, m)) | The walk stops at the first difference or when the shorter list ends |
| Space | O(1) | Two pointers (the arrays only exist to build the demo lists) |
result === 0), or ordering lists lexicographically, for example when sorting a list of lists.curr1 === curr2) is a different question: it tests whether two lists share a node, not whether their values are equal.[1, 2] and [1, 2, 3] as equal.curr1.val after curr1 has become null; check both pointers in the loop condition.curr1 === curr2) instead of values (curr1.val === curr2.val).curr1 and curr2 moving forward in step along their own lists.null.Input: list1 = [1, 2, 3], list2 = [1, 2, 4]
Output: -1
// Returns -1 if list1 < list2, 0 if they are equal, 1 if list1 > list2
// (lexicographic order, like comparing words letter by letter).
function compareLists(values1, values2) {
const list1 = buildList(values1);
const list2 = buildList(values2);
let curr1 = list1;
let curr2 = list2;
while (curr1 !== null && curr2 !== null) {
if (curr1.val < curr2.val) return -1;
if (curr1.val > curr2.val) return 1;
// Equal so far: move both pointers one node forward.
curr1 = curr1.next;
curr2 = curr2.next;
}
// One list ran out first (or both did).
if (curr1 === null && curr2 === null) return 0; // same length, all equal
if (curr1 === null) return -1; // list1 is a shorter prefix of list2
return 1; // list2 is a shorter prefix of list1
}
function buildList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = new ListNode(values[i], head);
}
return head;
}