Вращение LinkedList со значением k - PullRequest
Новая
       31

Вращение LinkedList со значением k

0 голосов
/ 28 мая 2019

Чтобы повернуть связанный список с k узлами, я пробую подход, при котором я пересекаю список, используя необязательный узел. У кода есть ошибка на шаге, где я «цепью» список

Алгоритм прост

  1. Используйте переменную "fast", начните с головы и двигайтесь к индексу k с головы
  2. Использовать переменную "медленно", начиная с головы
  3. Одновременно двигайтесь "быстро" и "медленно"
  4. Когда «быстрый» попадет в конец списка, начните цепочку (установив последний узел рядом с текущей головкой) и назначьте новый узел заголовка 
public class ListNode {
    public var value: Int
    public var next: ListNode?
    public init(value: Int, next: ListNode? = nil) {
        self.value =  value
        self.next = next
    }
}

extension ListNode: CustomStringConvertible {
    public var description: String {
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) -> " + String(describing: next) + " "
    }
}

func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {

    guard let head = head else { return nil }

    var fast = head
    var slow = head

    for _ in 0..<k where fast.next != nil {
        fast = fast.next!
    }

    while fast.next != nil {
        slow = slow.next!
        fast = fast.next!
        print("fast \(fast.value) slow \(slow.value)")
    }

    let new_head = slow.next!
    slow.next = nil
    fast.next = head

    return new_head
}

let node: ListNode = {
    let one = ListNode(value: 1)
    let two = ListNode(value: 2)
    let three = ListNode(value: 3)
    let four = ListNode(value: 4)
    let five = ListNode(value: 5)
    one.next = two
    two.next = three
    three.next = four
    four.next = five
    five.next = nil
    return one
}()

print(node.description)
rotateRight(node, 3)
print(node.description)

У меня «ошибка: выполнение было прервано, причина: EXC_BAD_ACCESS (код = 2, адрес = 0x7ffee108af98)». при беге на детской площадке

Ошибка, кажется, в строке fast.next = head, но я не понимаю, что не так с этой логикой!

...