JavaScript реверс из перевернутого массива в связанный список

алгоритм
JavaScript реверс из перевернутого массива в связанный список

Я уже писал похожие статьи до того, как связанный список был перевернут, но теперь я читаю статьи, которые я написал раньше, и я чувствую, что они слишком кратки, я просто разместил код и не рассказал основные вещи. Пользуясь выходными, давайте реорганизуем этот простой вопрос.

Как перевернуть массив?

Как мы все знаем, массивы JavaScript предоставляют множество полезных методов для работы с массивами, среди которыхArray.prototype.reverseспособ инвертировать числа в массиве. использоватьreverseЭта функция очень проста для реверсирования массива, вот как работает код:

let array = [1, 2, 3, 4, 5]
array.reverse()     // [5, 4, 3, 2, 1]

Такой код очень прост, но мы пока не знаем, как его реверсировать. Давайте взглянем на следующую распространенную идею — обмен головой и хвостом, как показано ниже:
Длина массива равна 3:

  • 1
  • 2
  • 3
  • 3
  • 2
  • 1

Длина массива равна 4:

  • 1
  • 2
  • 3
  • 4
  • 4
  • 2
  • 3
  • 1
  • 4
  • 3
  • 2
  • 1
Длина массива равна 5:
  • 1
  • 2
  • 3
  • 4
  • 5
  • 5
  • 2
  • 3
  • 4
  • 1
  • 5
  • 4
  • 3
  • 2
  • 1

Итак, длинаnМассив нужно поменять местамиn / 2 + 1раз, из этого мы можем получить следующий код:

let array = [1, 2, 3, 4, 5]
for(let i = 0; i < array.length / 2; i ++){
    [array[i], array[array.length - i - 1]] = [array[array.length - i - 1], array[i]]
}
console.log(array)  // [5, 4, 3, 2, 1]

Как перевернуть связанный список?

Что такое связанный список? Насколько я понимаю, длинаn, не может быть пройден через индексы и может получить доступ к структуре цепочки следующего узла только через текущий узел. Итак, без лишних слов, давайте создадим простой связанный список:

//节点构造函数
function Node(val){
    this.val = val
    this.next = null
}
//定义链表
function List(array){
    this.head = null
    let i = 0,temp = null
    while(i < array.length){
        if( i === 0){
            this.head = new Node(array[i])
            temp = this.head
        }else{
            let newNode = new Node(array[i])
            temp.next = newNode
            temp = temp.next
        }
        i++
    }
}
//遍历链表
function traverseList(listHead){
    while(listHead){
        console.log(listHead.val)    
        listHead = listHead.next
    }
}

Выше приведена простая реализация связанного списка, друзья, которые не понимают, могут его посмотреть.Структуры данных и алгоритмыСледующий фокус:Связанный список может получить доступ только к следующему узлу из текущего узла и не может получить доступ к элементам связанного списка через индексы.
Сначала не додумался, потом применил довольно странный способ - сохранить значение связанного списка в массив, инвертировать массив и потом переназначить значение, код такой:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    let temp = head,
        result = []
    while (temp != null) {
        result.push(temp.val)
        temp = temp.next
    }
    temp = head, i = 0
    result.reverse()
    while (temp != null) {
        temp.val = result[i++]
        temp = temp.next
    }
    return head
};

Но при этом явно не используются преимущества характеристик связанного списка, то есть текущий узел обращается к следующему узлу. Позже я былLeetCodeОбсуждение видит этот ход мысли ——Частичный реверс представляет собой глобальный реверс.Что ты имеешь в виду? Например:

  • 1
  • 2
  • 3
  • 4
  • 2
  • 1
  • 3
  • 4
  • 3
  • 2
  • 1
  • 4
  • 4
  • 3
  • 2
  • 1
Вдохновившись описанным выше процессом, мы можем легко получить следующий код:
var reverseList = function (head) {
    let pre = null
    while (head) {
        next = head.next
        head.next = pre
        pre = head
        head = next
    }
    return pre
};

Идея очень проста? В то время мне не пришла в голову такая простая идея... Размышляя...

Суммировать

От обращения массива к обращению связного списка можно сделать вывод: мышление не может быть ригидным (побег, алгоритм вроде бы очень распространенный---обратный, есть много способов сделать это. Друзья проходя мимо знаю другие Алгоритмы, подскажите пожалуйста

Отсканируйте приведенный ниже QR-код или найдите «Учебный класс мистера Тони» и подпишитесь на мою общедоступную учетную запись WeChat, после чего вы сможете получать мои последние статьи как можно скорее.

Категории