добавить два числа, представленные связанным списком в Scala

Question

Я новичок в scala и хочу написать код, который добавит два числа, представленных связанным списком в scala, в соответствии с приведенным ниже примером

Входной сигнал: Первый список: 5-> 6-> 3 // представляет номер 365 Второй список: 8-> 4-> 2 // представляет число 248 Выход Результирующий список: 3-> 1-> 6 // представляет номер 613

Я реализовал код изменяемого односвязного списка в scala для добавления, обновления и вставки элементов в связанный список. Найдите мой код ниже

    class SinglyLinkedList[A] extends ListADT[A] {
  private class Node(var data: A,var next: Node)
  private var head: Node = null
  def apply(index: Int): A = {
    require(index >= 0)
    var rover = head
    for (i <- 0 until index) rover = rover.next
    rover.data
  }
  def update(index: Int,data: A): Unit = {
    require(index >= 0)
    var rover = head
    for (i <- 0 until index) rover = rover.next
    rover.data = data
  }

  def insert(index: Int,data: A): Unit = {
    require(index >= 0)
    if(index == 0) {
      head = new Node(data, head)
    }
    else{
      var rover = head 
      for (i <- 0 until index-1) 
        rover = rover.next
        rover.next = new Node(data, rover.next)
    }
  }
  def remove(index: Int): A = {
    require(index >= 0)
    if(index == 0){
      val ret = head.data
      head = head.next
      ret
      } else {
   var rover = head 
      for (i <- 0 until index-1) rover = rover.next
        val ret = rover.next.data
        rover.next = rover.next.next
        ret
      }
  }


}

Может кто-нибудь сообщить мне, как я собираюсь выполнить сложение двух чисел, представленных в связанном списке.

Answer 1

Попробуйте это:

def add(a: List[Int], b: List[Int], o: Int): List[Int] = (a,b,o) match {
  case (x::xs, y::ys, d) =>
    val v = d + x + y
    (v%10)::add(xs, ys, v/10)
  case (Nil, Nil, 0) => Nil
  case (Nil, Nil, d) => d::Nil
  case (xs, Nil, d) => add(xs, 0::Nil, d)
  case (Nil, ys, d) => add(0::Nil, ys, d)
}

Answer 2

Как работает сложение? Я имею в виду сложение на бумаге: одно число под другим?

Давайте попробуем за 465 + 248

  465
+ 248
  ---

Мы начинаем с наименее значимых цифр: 5 + 8. Но 5 + 8 = 13, поэтому результат не уместится в одну цифру. Вот почему мы поступаем так, как нас учил учитель в дошкольных учреждениях: мы оставляем единичную цифру и переносим десятки в следующую колонку

   1
  465
+ 248
  ---
    3

Теперь десятки. 6 + 4 + (несут) 1 = 11. Снова оставляем 1 и переносим 1 в следующий столбец:

  11
  465
+ 248
  ---
   13

И последний столбец. 4 + 2 + 1 = 7.

  11
  465
+ 248
  ---
  713

Таким образом, результат равен 713. Если на одно из этих двух чисел добавлено больше столбца, или в последнем добавлении вы перенесли бы его, вы можете просто переписать оставшиеся числа.

С неизменным списком избранного он будет работать точно так же (я сейчас объясню, почему я использовал неизменный):

1. взять оба списка
2. взять заголовки обоих списков (если один из них пуст, вы можете просто вернуть другой в результате добавления)
3. добавить головы и разделить результат на перенос и текущую цифру (перенос будет 0 или 0, цифра от 0 до 9)
4. если есть carry > 0 добавить список carry :: Nil к одному из хвостов рекурсивно
5. префикс числа к рекурсивно добавленным хвостам

У вас должно получиться что-то вроде этого:

val add: (List[Int], List[Int]) => List[Int] = {
  case (a :: as, b :: bs) => 
    val digit = (a + b) % 10
    val carry = (a + b) / 10
    if (carry > 0) digit :: add(add(as, carry :: Nil), bs)
    else digit :: add(as, bs)
  case (as, Nil)   => as
  case (Nil, bs) => bs
} 

add(5 :: 6 :: 4 :: Nil, 8 :: 4 :: 2 :: Nil) // 3 :: 1 :: 7 :: Nil

Теперь, если бы вы использовали изменяемый список, это было бы сложнее. Если вы хотите использовать изменяемый список, вы хотите обновить один из них, верно? Какой - первый? Во-вторых? И то и другое? Ваш алгоритм может вычислить правильный результат, но разделить ввод.

Допустим, вы всегда добавляете второй список в первый и хотите оставить второй нетронутым. Если второй список длиннее, и вам нужно будет добавить несколько новых мест для цифр, вы должны скопировать все оставшиеся сегменты (в противном случае вы можете, например, обновить один номер во втором списке и изменить первый). Вам также придется обращаться с угловым футляром с переносом.

Довольно нелогичное поведение - числа не изменяемы, и вы хотите представлять числа.