How does my LinkedList merge two lists solution compare?

📚 Official Books Data Structures & Algorithms in Swift
1

This is what I came up with for LinkedList “Challenge 4: Merge two lists”:

func mergeSorted<T: Comparable>(_ left: LinkedList<T>,
                                _ right: LinkedList<T>) -> LinkedList<T> {
    guard !left.isEmpty else { return right }
    guard !right.isEmpty else { return left }

    var list = LinkedList<T>()

    var leftNode = left.head
    var rightNode = right.head

    while leftNode != nil || rightNode != nil {
        if let unwrappedLeftNode = leftNode, let unwrappedRightNode = rightNode {
            if unwrappedLeftNode.value < unwrappedRightNode.value {
                list.append(unwrappedLeftNode.value)
                leftNode = leftNode?.next
            } else {
                list.append(unwrappedRightNode.value)
                rightNode = rightNode?.next
            }
        } else if let unwrappedLeftNode = leftNode {
            list.append(unwrappedLeftNode.value)
            leftNode = leftNode?.next
        } else if let unwrappedRightNode = rightNode {
            list.append(unwrappedRightNode.value)
            rightNode = rightNode?.next
        }
    }

    return list
}

How does this compare to the official solution? Maybe I’m wrong, but I think mine is shorter and a little bit easier to reason about. The official one runs in O(n + m) time, and I think mine does as well. The official one has an optimization where if it runs out of nodes for one of the two lists, it sets tail?.next = leftNode or tail?.next = rightNode, so it skips iterating over the remaining nodes, but then it iterates over the remaining nodes anyway further down with while let next = tail?.next { ... }.

What do you all think?

2

I think your solution is better because does not impact original lists. Clever usage of one while loop.
Here is my solution:

func mergeSorted<T: Comparable>(_ left: LinkedList<T>,
                                _ right: LinkedList<T>) -> LinkedList<T> {
  guard !left.isEmpty else {
    return right
  }
  guard !right.isEmpty else {
    return left
  }
  
  var list = LinkedList<T>()
  var currentLeft = left.head
  var currentRight = right.head
  
  while let leftValue = currentLeft?.value, let rightValue = currentRight?.value {
    if leftValue <= rightValue {
      list.append(leftValue)
      currentLeft = currentLeft?.next
    } else {
      list.append(rightValue)
      currentRight = currentRight?.next
    }
  }
  
  var finalNodes: Node<T>?
  if let leftNodes = currentLeft {
    finalNodes = leftNodes
  }
  if let rightNodes = currentRight {
    finalNodes = rightNodes
  }
  
  while let value = finalNodes?.value {
    list.append(value)
    finalNodes = finalNodes?.next
  }
  
  return list
}
1 Like