Daily Coding Problem: Problem #256 [Medium]

Given a linked list, rearrange the node values such that they appear in alternating low -> high -> low -> high ... form.

For example, given 1 -> 2 -> 3 -> 4 -> 5,

you should return 1 -> 3 -> 2 -> 5 -> 4

package main

import (
	"fmt"
)

type Node struct {
	next *Node
	value int64
}

type List struct {
	head *Node
}

func (l *List) insert(data int64) *List {
	if l.head == nil {
		l.head  = &Node{next: nil, value: data}
	} else {
		l.head.insert(data)
	}

	return l
}

func (n *Node) insert(data int64) {
	if n == nil {
		return
	} else if n.next  == nil {
		n.next = &Node{next: nil, value: data}
	} else {
		n.next.insert(data)
	}
}

func (l *List) Display() {
    list := l.head
    for list != nil {
        fmt.Printf("%+v ->", list.value)
        list = list.next
    }
    fmt.Println()
}
 
func Display(list *Node) {
    for list != nil {
        fmt.Printf(" %v -> ", list.value)
        list = list.next
    }
    fmt.Println()
}


// Arrange func return 
func (list *List) Arrange() {

	if list == nil {
		return
	}

	prev := list.head
	curr := list.head.next

	for curr != nil {
		if prev.value > curr.value {
			temp := prev.value
			prev.value = curr.value
			curr.value = temp
		}

		if curr.next != nil && curr.next.value > curr.value {
			temp := curr.value
			curr.value = curr.next.value
			curr.next.value = temp
		}

		prev = curr.next

		if curr.next == nil {
			break
		}

		curr = curr.next.next
	}

}

func main() {
	list := &List{}
	list.insert(10).
		 insert(20).
		 insert(30).
		 insert(40).
		 insert(50)
	

	list.Arrange()
	fmt.Println("Arrange nodes in linked list")
	list.Display()

}

The time complexity of above solution is O(n) and space complexity is O(1)