700071. Compare two linked lists
Compare two linked lists
Slug: compare-two-linked-lists
Difficulty: Easy
Id: 700071
Topic Tags: Linked List, Data Structures
Company Tags: None
Summary
Compare two linked lists and determine if they are identical or not. This problem is about comparing the elements of two linked lists to check if they are equal.
Detailed Explanation
The algorithmic approach for this problem involves iterating over both linked lists simultaneously and comparing their elements. We can start by initializing pointers for both linked lists at the beginning. Then, we iterate until one of the linked lists reaches its end (i.e., null). In each iteration, we compare the current nodes of both linked lists. If they are equal, we move on to the next nodes in both linked lists. If they are not equal, or if one linked list has reached its end and the other hasn't, we can conclude that the two linked lists are not identical.
Here is a step-by-step breakdown of the solution:
- Initialize pointers for both linked lists at the beginning.
- Iterate until one of the linked lists reaches its end (i.e.,
null). - In each iteration, compare the current nodes of both linked lists.
- If they are equal, move on to the next nodes in both linked lists.
- If they are not equal, or if one linked list has reached its end and the other hasn't, conclude that the two linked lists are not identical.
Time complexity: O(n), where n is the length of the longer linked list. This is because we visit each node once.
Space complexity: O(1), as we only use a constant amount of space to store the pointers for the linked lists.
Optimized Solutions
Java
public boolean compareLists(ListNode head1, ListNode head2) {
while (head1 != null && head2 != null) {
if (head1.val != head2.val)
return false;
head1 = head1.next;
head2 = head2.next;
}
return head1 == null && head2 == null;
}