1->2->3->4 + 5->6->7->8 ==> 1->2->3->4->5->6->7->8
1->2->3->4 + 1->2->7->9 ==> 1->1->2->2->3->4->7->9
1->2->3->4 + null ==> 1->2->3->4
Lists
.
1. Create a temporary newHead
node.
2. Assuming the function takes in two nodes as input parameters, write the base condition to return
one of the nodes when the other node becomes null
or both are null
.
3. Compare the data in the first nodes of the two lists. If the data in the first node of the first list is
smaller than that of the second list, assign the first node of the first list to the newHead
.
To find the next node in the merged list,
do newHead.next = mergeTwoSortedList(l1.next, l2)
.
4. Else, if the data in the first node of the second list is
smaller than that of the first list, assign the first node of the second list to the newHead
.
To find the next node in the merged list,
do newHead.next = mergeTwoSortedList(l2.next, l1)
.
5. Return newHead
node.
public ListNode mergeTwoSortedList(ListNode l1, ListNode l2) { }
C
Java
Python