CODEWITHSUNDEEP
swiftdata-structures
stevenpcurtis
stevenpcurtis

Reputation: 2001

Reverse a linked list in Swift

Reversing a linked list in Swift is easy. I have a working solution. However, while preparing for whiteboard interviews the version I produce quickly simply does not work and I cannot identify why.

I need to know why the following does not work - from the Playground I believe it is because 

tail = previous

line errors and execution never completes.

func reverseLL (node: Node?) -> Node? {
    guard node != nil else { return nil }
    var tail : Node? = node
    var previous = node?.next
    while previous != nil {
        let tailRef = previous?.next
        previous?.next = tail
        tail = previous
        previous = tailRef
    }
    return tail
    }

My definition of the linked list is:

class Node: CustomStringConvertible {
    var data: Int
    var next: Node?

    var description: String {
        return String(data) + (next != nil ? next!.description : "")
    }

    init (data: Int) {
        self.data = data
        next = nil
    }

    func appendToTail(data: Int) {
        if (next != nil) {
            next?.appendToTail(data: data)
        }
        else {
            next = Node(data: data)
        }
    }
}

My working version of reverseLL (which I accept is more 'Swifty') is as follows, but I believe it should be functionally identical to my earlier definition.

 func reverseLL (node: Node?) -> Node? {
guard node != nil else { return nil }
        var tail: Node?
        var headNode = node
        while let head = headNode {
            let tailRef = head.next
            head.next = tail
            tail = head
            headNode = tailRef
        }
        return tail
    }

So creating a linked list with

let ll = Node(data: 3)
ll.appendToTail(data: 4)
ll.appendToTail(data: 4)
ll.appendToTail(data: 5)

gives the data in order of 3445

and reversed through

reverseLL(node: ll)

gives the data in order of 5443

To be clear, why does the 

tail = previous

line halt execution in my first definition of reverseLL?

Upvotes: 0

Views: 2164

Answers (2)

Ruchin Somal
Ruchin Somal

Reputation: 1103

Here is the complete code including class, function and input and output things

// First we are creating class to store the data of Linked List

class Node {
    var data: Int
    var next: Node?

    var description: String {
        return String(data) + (next != nil ? next!.description : "")
    }

    init (data: Int) {
        self.data = data
        next = nil
    }

    func appendToLast(data: Int) {
        if (next != nil) {
            next?.appendToLast(data: data)
        } else {
            next = Node(data: data)
        }
    }
}

//Function that return the reversed Linked List

func reverseLinkedList(node: Node?) -> Node? {
guard node != nil else { return nil }
        var tail: Node?
        var headNode = node
        while let head = headNode {
            let tailRef = head.next
            head.next = tail
            tail = head
            headNode = tailRef
        }
        return tail
    }

//Input all the data which we have in the linkedlist and output of that inside the print function.

let ll = Node(data: 3)
ll.appendToLast(data: 4)
ll.appendToLast(data: 4)
ll.appendToLast(data: 5)
let reversedLL = reverseLinkedList(node: ll)
print(reversedLL?.description ?? "No Data")

Upvotes: 1

ielyamani
ielyamani

Reputation: 18591

The second version is more Swifty since you're using optional binding and avoiding the horrendous forced-unwrapping.

The problem in the first version is that tail is initially equal to node. In the example that you've given that is (3->4->4->5).

So when you do previous?.next = tail in the first iteration, previous becomes (4->4->5->3->4->5->3->4->5->...). Notice that The node with data equal to 5 now points to a node with data equal to 3. Which creates an infinite loop.

Simplification

The guard statement could also be written as :

guard node?.next != nil else {
    return node
}

which would include lists with a single node.

Upvotes: 1

Related Questions