Разворот связанного списка

Легкая

04 December 2023

Описание задачи #

Вам дан односвязный список. Переверните список и верните его.

Список представлен следующей структурой.

type ListNode struct {
    Val  int
    Next *ListNode
}

class ListNode {
    val: number
    next: ListNode | null
}

Ограничения #

Количество узлов в связанном списке находится в диапазоне от 1 до 5000
Значение каждого узла находится в диапазоне от -5000 до 5000

Примеры #

Решение #

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

Реализация #

package reverse_linked_list

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head

	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}

	return prev
}

export class ListNode {
    val: number
    next: ListNode | null

    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}

export const reverseList = (head: ListNode | null): ListNode | null => {
    let prev: ListNode | null = null
    let curr = head

    while (curr) {
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }

    return prev
}

Оценка сложности #

По времени

Сложность O(n), так как мы итерируемся по всем узлам списка.

По памяти

Сложность O(1), так как мы не выделяем дополнительную память.

Оригинал задачи на Leetcode

Algorithmics