Skip to content

Instantly share code, notes, and snippets.

@pmillssf
Last active December 6, 2017 03:53
Show Gist options
  • Save pmillssf/fe78f2b34354f250950db86af0d49b89 to your computer and use it in GitHub Desktop.
Save pmillssf/fe78f2b34354f250950db86af0d49b89 to your computer and use it in GitHub Desktop.
Write up for how to merge two sorted linked lists

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment