Реверсивный список узлов

Question

У меня есть следующий класс Node, который указывает на следующий узел:

class Node<T> {
    var data: T
    var next: Node<T>?

 init(data: T, next: Node<T>?) {
        self.data = data
        self.next = next
    }
}

, и я написал метод для обратного преобразования данных, например

let list = Node<Int>(data:1,next :Node<Int>(data:2,next :Node<Int>(data :3,next :nil)))

, который имеет значения 1 , 2,3 должны иметь значения 3,2,1 вот моя функция:

    extension Node {
        func reverse() {

        var firstNode = self
         var previousNode: Node<T>? = nil
        var currentNode = firstNode
        var nextNode = firstNode.next
        while nextNode != nil {

            currentNode.next = previousNode
            previousNode = currentNode
            currentNode = nextNode!
            nextNode = currentNode.next
        }

        currentNode.next = previousNode
        firstNode = currentNode


        var current = firstNode as Node<T>?
       //print 3 2 1
        while(current != nil)
        {
          print(current!.data)
          current = current!.next

        }


        }
    }

Печать в методе действительно отображает «3 2 1», однако, как я могу установить его для текущего объекта на быть обратным списком? Назначение в конце "self = current" похоже, запрещено.

Answer 1

У вас нет возможности узнать, какой у вас связанный список . Добавьте один:

class Node<T> : CustomStringConvertible {
    var data: T
    var next: Node<T>?
    init(data: T, next: Node<T>?) {
        self.data = data
        self.next = next
    }
    var description: String {
        var s = ""
        var node = Optional(self)
        while node != nil {
            s.append(String(describing:node!.data))
            node = node?.next
        }
        return(s)
    }
}

Теперь легко увидеть, что ваш reverse работает. Все, что вам нужно сделать, это дать ему значение.

extension Node {
    func reverse() -> Node? {
        var firstNode = self
        var previousNode: Node<T>? = nil
        var currentNode = firstNode
        var nextNode = firstNode.next
        while nextNode != nil {
            currentNode.next = previousNode
            previousNode = currentNode
            currentNode = nextNode!
            nextNode = currentNode.next
        }
        currentNode.next = previousNode
        firstNode = currentNode
        let current = firstNode as Node<T>?
        return current
    }
}

Вот тест:

    let list = Node<Int>(data:1,next :Node<Int>(data:2,next :Node<Int>(data :3,next :nil)))
    print(list) // 123
    if let newlist = list.reverse() {
        print(newlist) // 321, yay!
    }

Answer 2

Ваш list - это просто переменная Node<Int>, то есть указатель на головной узел.

Вы не можете изменить self, чтобы он был ссылкой на другой узел - хвостовой узел в исходный список, но вы можете вернуть последний узел и повторно назначить то, что list указывает на:

var list = Node<Int>(...)

list = list.reverse()

Функция reverse должна будет возвращать Node<T> тип:

func reverse() -> Node<T> {
   // your algorithm
   // ...


   return firstNode
}

Кстати, ваш код не учитывает циклы в списке. Если какой-то узел указывает на один из своих предыдущих узлов, тогда ваш while nextNode != nil станет бесконечным l oop.