# How does my LinkedList merge two lists solution compare?

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

guard !left.isEmpty else { return right }
guard !right.isEmpty else { return left }

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?

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

guard !left.isEmpty else {
return right
}
guard !right.isEmpty else {
return left
}

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