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)
Categories: #Data Structures & Algorithms Tags: #Coding #Golang