Merge Two Linked Lists in Swift

Hello everyone, Leo here. This is the swift algorithm series and today we’ll explore a very common linked list problem Merge two sorted linked lists in Swift.

Not very often when you are dealing with linked lists do you have to deal with pointers. One example is when you have to find if a linked list is cyclic or not you can do this by creating a slow pointer and a fast pointer traversing the list until they reach each other or one of them is nil.

You can check the problem here if you are curious.

No more talking, let’s code!

The Problem

You have two ordered linked lists and you want to merge then into one.

First, we will create a pretty basic linked list class:

class LinkedNode<T> {
    var next: LinkedNode<T>?
    var value: T
    
    init(next: LinkedNode<T>?, value: T) {
        self.next = next
        self.value = value
    }
    
    func printList() {
        
        var currentNode = self
        print(value)
        while currentNode.next != nil {
            currentNode = currentNode.next!
            print(currentNode.value)
        }
    }
    
}

let linkedNode5 = LinkedNode(next: nil, value: 5)
let linkedNode4 = LinkedNode(next: linkedNode5, value: 3)
let linkedNode3 = LinkedNode(next: linkedNode4, value: 2)
let linkedNode2 = LinkedNode(next: linkedNode3, value: 2)
let linkedListRoot = LinkedNode(next: linkedNode2, value: 1)

let linkedNode7 = LinkedNode(next: nil, value: 10)
let linkedNode6 = LinkedNode(next: linkedNode7, value: 9)
let linkedNode55 = LinkedNode(next: linkedNode6, value: 8)
let linkedNode44 = LinkedNode(next: linkedNode55, value: 6)
let linkedNode33 = LinkedNode(next: linkedNode44, value: 4)
let linkedNode22 = LinkedNode(next: linkedNode33, value: 3)
let linkedListRoot2 = LinkedNode(next: linkedNode22, value: 1)

This code will create two linked lists the linkedListRoot and the linkedListRoot2.

One thing to be considered is that I implemented the LinkedList as a class in swift. All the references for list1 and list2 are messed up, so WILL have an effect outside the merge function.

To surpass this you have to implement linkedLists as indirect enums, but this is a topic for another post here our focus is on the algorithm.

And now we will create the function to merge them into one.

Merging Linked List Algorithm

Below you can check how you can merge two linked lists in Swift.

func mergeLinkedLists(listOne: LinkedNode<Int>?, listTwo: LinkedNode<Int>?) {
    
    var list1 = listOne // 1
    var list2 = listTwo // 2
    
    let resultNodeHead = LinkedNode(next: nil, value: 0) // 3
    var currentNode : LinkedNode<Int>? = resultNodeHead // 4
    
    while list1?.value != nil && list2?.value != nil { // 5
        
        if list1!.value < list2!.value { // 5
            currentNode?.next = list1
            list1 = list1?.next
        } else {
            currentNode?.next = list2
            list2 = list2?.next
        }
        
        currentNode = currentNode?.next // 6
    }
    
    if list1 != nil { // 7
        currentNode?.next = list1
    }
    
    if list2 != nil { // 7
        currentNode?.next = list2
    }
    
    resultNodeHead.next?.printList() // 8
}

And that’s it, let’s explain it.

Code Explanation – Merge two sorted linked lists in Swift

On (1/2) mark we have to pass the reference to a ‘var’ because listOne and listTwo are default ‘let’ variables even if the type is reference type like in the example above. We could solve this using ‘inout’. The (1) is a dummy value and the only purpose is to give us a head pointer.

The (3) create our first pointer. This will always point to the head of the new linked list created and is what we return the (8) mark. In the (4) mark we create the node that will be selected to be always the next node. This node we use to keep updated the last inserted node in the linked list.

On (5) mark we traverse the two linked lists doing three things. First, we compare the actual node value of each one.

After that, we assign the current node’s next value to the compared value and on the (6) mark we just update the current node to the next position itself. This way we can run through all that again.

The two later phases are the core of this algorithm if we populate the next sorted value to the next current node and after that, we update the current node itself (update the pointer to the recently updated next value).

(7) are for the cases one linked list finished the traverse and the other one don’t. That way we have to assign the rest of the list to the next current.

And finally the (8) mark we have to show the next one because the head was a dummy value, so it will start on the next head value.

Time And Space Complexity

This algorithm’s time complexity is O(n) since we traverse only one time each of the linked lists. Space complexity is O(1) because the algorithm space is independent of the input since we’re just pointing to already created memory.

That’s it. I hope you enjoy this algorithm as I do and if you have any comments or feedback don’t hesitate to share.

Algorithms: Continue Studying

Merging linked lists is one of the basic algorithms to know when studying linked lists. Another basic algorithm is BFS, which you can use to solve the number of islands problem. In that problem, we use the BFS to traverse the array and manipulate the values so we don’t traverse two times the same node.

Another algorithm that is good to know but hardly you will have to implement in a real-world interview is the Trie data structure. In this article, I show how to implement the Trie data structure in Swift and how you can improve your code with a really interesting graph data structure.

Summary – Merge two sorted linked lists in Swift

That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks.

Credits – image