Write up for how to merge two sorted linked lists

mergeTwoSortedLinkedLists.md

Requirements

Merge two sorted linked lists.

• input: head of sorted linked list one, head of sorted linked list two
• output: head of linked list containing one and two merged
• constraints: the new list should be made by splicing together the nodes of the two lists
• edge cases: null inputs, duplicate values

Strategy

Iterative Strategy:

• Save the head of the smaller linked list to return
• Make a copy of that head
• While either linked list head isn't null
  • Set the next key of the copy to the smaller head
  • Set the copy equal to its' next node
  • Set the smaller head equal to its' next node
• Set the next key of copy to which ever linked list node isn't null
• Return the saved head

Recursive Strategy:

• If listA or listB is null, return the other one
• If listA is greater than listB,
  • listB next equals the recurisve call to (listA, listB.next)
  • return listB
• Else do the opposite

Justification of strategy

Iterative justification: Just iterating through both lists at the same time, going one node at a time, until one ends, and attaching the end of the other list.

Recursive justification: Were repeating the same basic step over and over, which makes this problem a great case for recursion.

Define test cases

1->2->3, 1->2->4 => 1->1->2->2->3->4

2->5->7, 3->6->8 => 2->3->5->6->7->8

1, null => 1

null, null => null

Implementation skeleton

Iterative

• if either input is null, return the non-null one
• set an output variable equal to the smaller of the two inputs
• set the smaller of the two inputs to equal its next
• set a currentOutput variable equal to output
• while listA and listB
  • if listA >= listB
    • currentOutput next is equal to listB
    • currentOutput is equal to currentOutput next
    • listB is equal to listB next
  • else
    • currentOutput next is equal to listA
    • currentOutput is equal to currentOutput next
    • listA is equal to listB next
• currentOutput next is equal to the non-null list
• return output

Recursive

• if listB is null, return listA
• if listA is null, return listB
• if listA > list B
  • listB next is equal to recursive call, (listA, listB.next);
  • return listB
• listA next is equal to recursive call, (listA.next, listB);
  • return listA

Actual implementation

https://repl.it/@pmillssf/MergeTwoSortedLinkedLists

Execute test cases

run the implementation

Big-O Analysis

time: o(n + m) size: o(1)

Optimization (if applicable)