Задача

Изменение порядка следования элементов связного списка

Сложность: Средняя

Условие задачи : дан связный список: 

L0 → L1 → … → Ln - 1 → Ln.

Надо переопределить порядок следования элементов на следующий: 

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Пример: 

Ввод: head = [1,2,3,4]

Вывод: [1,4,2,3]

Ввод: [1,2,3,4,5]

Вывод: [1,5,2,4,3]

Решение задачи:

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    if head == nil {return}
    
    var slice []*ListNode
    tmp := head
    for tmp != nil  {
        slice = append(slice, tmp)
        tmp = tmp.Next
    }

    l, r := 0, len(slice) - 1
    for l < r {
        slice[r].Next = nil
        slice[l].Next = slice[r]
        l++ 
        slice[r].Next = slice[l]
        slice[l].Next = nil
        r--
    }

    head = slice[0]
}