Перестройка связанного списка

Перестройка связанного списка

Условие задачи

Дана голова односвязного списка. Измените список так, чтобы узлы второй половины в обратном порядке чередовались с узлами первой половины. Например, список

1

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nil

нужно преобразовать в

1

1 -> 6 -> 2 -> 5 -> 3 -> 4 -> nil

Алгоритм не должен использовать дополнительную память и должен изменять исходный список на месте.

Примеры:

1
2
3
4
5

Вход:  2 -> 4 -> 6 -> 8 -> 10 -> 12 -> nil
Выход: 2 -> 12 -> 4 -> 10 -> 6 -> 8 -> nil

Вход:  2 -> 4 -> 6 -> 8 -> 10 -> nil
Выход: 2 -> 10 -> 4 -> 8 -> 6 -> nil

Решение

Задача похожа на проверку списка на палиндром:

  1. Найдём средний узел быстрым и медленным указателями.
  2. Инвертируем вторую половину списка.
  3. Поочерёдно соединим узлы первой половины и инвертированной второй половины.
  4. Установим ссылку последнего узла в nil, чтобы список завершался корректно.

Код

Вот как будет выглядеть наш алгоритм:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

package main

import "fmt"

type ListNode struct {
	Value int
	Next  *ListNode
}

func reorder(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}

	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	firstHalf := head
	secondHalf := reverseList(slow)

	for firstHalf != nil && secondHalf != nil {
		nextFirst := firstHalf.Next
		firstHalf.Next = secondHalf
		firstHalf = nextFirst

		nextSecond := secondHalf.Next
		secondHalf.Next = firstHalf
		secondHalf = nextSecond
	}

	if firstHalf != nil {
		firstHalf.Next = nil
	}
}

func reverseList(head *ListNode) *ListNode {
	var previous *ListNode
	current := head

	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}

	return previous
}

func newList(values ...int) *ListNode {
	dummy := &ListNode{}
	current := dummy

	for _, value := range values {
		current.Next = &ListNode{Value: value}
		current = current.Next
	}

	return dummy.Next
}

func printList(head *ListNode) {
	for current := head; current != nil; current = current.Next {
		if current != head {
			fmt.Print(" -> ")
		}
		fmt.Print(current.Value)
	}
	fmt.Println()
}

func main() {
	even := newList(2, 4, 6, 8, 10, 12)
	reorder(even)
	printList(even)

	odd := newList(2, 4, 6, 8, 10)
	reorder(odd)
	printList(odd)
}

Вывод:

1
2

2 -> 12 -> 4 -> 10 -> 6 -> 8
2 -> 10 -> 4 -> 8 -> 6

Временная сложность

Поиск середины, инвертирование и слияние половин выполняются за линейное время. Общая временная сложность равна \(O(N)\).

Пространственная сложность

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).