swift - 从反向链表中提取值

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.

一个例子:

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

That is: 617 + 295.

Output: 2 -> 1 -> 9.

That is: 912.

为了开始这个问题，我首先创建了一个定义链表的类:

第一步:定义链表

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
    }
}

步骤:2 - 根据用户输入的整数值生成链表

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

然后我继续使用以下函数反转链表。

第三步:反转链表

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

第 4 步:这一步背后的想法是提取每个节点上的值，将它们转换为字符串，然后将它们连接到字符串变量，最后将字符串值转换为 Int，然后使用该 Int值并最终添加它们。

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)!
}

这是我遇到问题的地方:

当我像这样将以下内容插入此函数时:

getValuesFrom(head: reversedList)

我收到以下错误:

fatal error: unexpectedly found nil while unwrapping an Optional value

而且我似乎无法弄清楚为什么我会遇到问题，非常感谢任何形式的见解。

Answer 1

String和链表之间不需要来回转换，只是为了打印结果。这样做很简单:

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"
    }
  }
}

现在您可以:

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

鉴于您的问题，也无需反转列表。

如前所述，要对列表求和，请转换为 Int，添加它们，然后生成一个新列表:

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
  }
}

那么你所需要的就是重载加法运算符......

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

并测试...

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

结果:

7 -> 1 -> 6 -> nil

5 -> 9 -> 2 -> nil

2 -> 1 -> 9 -> nil