CODEWITHSUNDEEP
swiftstringlinked-listsingly-linked-list
user5618798
user5618798

Reputation:

Extracting values from a reversed linked list

Question:

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

An Example:

Input: (7-> 1 -> 6) + (5 -> 9 -> 2).

That is: 617 + 295.

Output: 2 -> 1 -> 9.

That is: 912.

In order to begin with this question, I first created a class that would define what a linked list:

Step 1: Defining the linked list

class Node: CustomStringConvertible{
    var value: Int
    var next: Node?
    var description: String{
        if next != nil {
          return "\(value) -> \(next!)"
        }
        else{
            return "\(value) -> \(next)"
        }
    }
    init(value: Int) {
        self.value = value
    }
}

Step: 2 - Generated the linked list, from user input of integer values

func generateList (num: Int) -> Node {
    var stringNum = Array(String(num).characters)
    let head = Node.init(value:Int(String(stringNum.first!))!)
    var current = head

    for i in 1..<stringNum.count{
        let num = Int(String(stringNum[i]))
        current.next = Node.init(value: num!)
        current = current.next!
    }
    return head
}

let list = generateList(num: 716)

// The following prints out: 7 -> 1 -> 6 -> nil

Then I proceeded over to reverse the linked list using following function.

Step 3: Reverse the linked list

func reverseLinkedList (head: Node?) -> Node?{

    var current = head
    var prev: Node?
    var next: Node?

    while current != nil {
        next = current?.next
        current?.next = prev
        prev = current
        current = next
    }
    return prev
}

let reversedList = reverseLinkedList(head: list)

// The following prints out is: 6 -> 1 -> 7 -> nil

Step 4: The idea behind this step is to extract the values on each of the nodes, cast them as a string and then concatenate them to a string variable and then lastly cast the string value into an Int and then use that Int value and eventually add them.

func getValuesFrom (head: Node?) -> Int {

    var string = ""
    var current = head

    while current != nil {
        var stringVal = String(describing: current?.value)
        string += stringVal
        current = current?.next
    }

    return Int(string)!
}

Here is where I am having a problem:

When I plug in the following into this function like so: 

getValuesFrom(head: reversedList)

I get the following error:

fatal error: unexpectedly found nil while unwrapping an Optional value

And I can't seem to figure out why I having a problem and would really appreciate any sort of insight.

Upvotes: 1

Views: 490

Answers (1)

user887210
user887210

Reputation:

There is no need to convert back and forth between String and the linked list, except to print it for results. This is done simply like this:

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

  // init and generator can be the same method
  init(value: Int) {
    // store ones place and divide by 10
    self.value = value % 10
    var nextValue = value / 10

    // set up for loop
    var currentNode = self

    while nextValue > 0 {
      // create a new Node
      // store ones place and divide by 10
      let next = Node(value: nextValue % 10)
      nextValue /= 10

      // make the new Node the next Node
      currentNode.next = next

      // set up for next iteration
      currentNode = next
    }
  }
}

// make the list printable
extension Node: CustomStringConvertible {
  var description: String{
    if let next = next {
      return "\(value) -> \(next)"
    }
    else {
      return "\(value) -> nil"
    }
  }
}

Now you can do:

print(Node(value: 671)) // prints "7 -> 1 -> 6 -> nil"

There is also no need to reverse the lists, given your question.

To sum the lists you can do just as you've said, convert to an Int, add them, then generate a new list:

extension Node {
  func toValue() -> Int {
    var place = 10
    var current = self
    // add each value and multiply by the place value
    // first is 1, second 10, third 100, etc.
    var result = current.value
    while let next = current.next {
      result += next.value * place
      place *= 10
      current = next
    }
    return result
  }
}

Then all you need is to overload the addition operator...

func +(lhs: Node, rhs: Node) -> Node {
  return Node(value: lhs.toValue() + rhs.toValue())
}

and test...

let first = Node(value: 617)
let second = Node(value: 295)
print(first)
print(second)
print(first + second)

Result:

7 -> 1 -> 6 -> nil

5 -> 9 -> 2 -> nil

2 -> 1 -> 9 -> nil

Upvotes: 0

Related Questions