Merging two sorted linked lists in Swift

Subscribe to my newsletter and never miss my upcoming articles

Hello everyone, Leo here.

This is the swift algorithm series and today we'll explore a very common linked list problem. Not very often when you are dealing with linked lists 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 then 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 because I implemented the LinkedList as a class in swift, all the references for the list1 and list2 are messed up, so WILL have effect outside the merge function. To surpass this you have to implement linkedLists as indirected enums, but this is topic for other post here our focus are in the algorithm.

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

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
}

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 exemplo 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 (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 in the linked list.

On (5) mark we traverse the two linked list doing three things. First we compare the actual node value of each one. After that we assign the current node next value to the compared value and on (6) mark we just update the current node to the next position of itself, so we can run through all this again. The two later phases are the core of this algorithm, inside the if we populate the next sorte 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, so we have to assign the rest of the list to next of the 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 of the head.

Time And Space Complexity

This algorithm time complexity is O(n) since we traverse only on time each of the linked lists and space complexity is O(1) because the algorithm space are 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 feedbacks don't hesitate to share.

Thanks for reading and... That's all folks!

No Comments Yet