Merge Lists Alternatingly

Slug: merge-list-alternatingly

Difficulty: Easy

Id: 700588

Topic Tags: Linked List, Data Structures

Company Tags: Amazon

Summary

This problem involves merging two linked lists in an alternating manner. The goal is to create a new linked list where elements from the first list and then elements from the second list are appended until one of the lists becomes empty.

Detailed Explanation

To solve this problem, we'll iterate through both linked lists simultaneously. We'll maintain two pointers, head1 and head2, pointing to the current nodes in each list. We'll create a new linked list, result, to store the merged elements.

Here's a step-by-step breakdown of the solution:

Initialize result as an empty linked list.
Loop until one of the lists becomes empty:
- If head1 is not null, append its value to result and move head1 forward by one node.
- If head2 is not null, append its value to result and move head2 forward by one node.
Return the merged linked list.

Time complexity: O(n + m), where n and m are the lengths of the input lists. Space complexity: O(n + m) for the new linked list.

Optimized Solutions

Java

public ListNode mergeLists(ListNode head1, ListNode head2) { ListNode result = null; while (head1 != null || head2 != null) { if (head1 != null) { if (result == null) { result = head1; } else { addTail(result, head1.val); } head1 = head1.next; } if (head2 != null) { if (result == null) { result = head2; } else { addTail(result, head2.val); } head2 = head2.next; } } return result; }