I have written the following program in Go to mergesort a singly linked list. It does bottom up merge sort and hence does not have to find the mid of the linked list. Please review the algorithm and the code for idiomatic Go.
package main
import (
"fmt"
)
type node struct {
val int
next *node
}
type list struct {
head *node
}
func newList(arr []int) *list {
if arr == nil || len(arr) == 0 {
return nil
}
l := new(list)
l.head = getNode(arr[0])
prev := l.head
for i := 1; i < len(arr); i++ {
n := getNode(arr[i])
prev.next = n
prev = n
}
return l
}
func printList(n *node) {
for p := n; p != nil; p = p.next {
fmt.Printf("%d ", p.val)
}
}
func getNode(v int) *node {
n := new(node)
n.val = v
return n
}
func skip(n *node, len int) (fast *node, slow *node) {
counter := 0
fast = n
slow = n
for counter < len {
if fast != nil && fast.next != nil {
fast = fast.next.next
} else if fast != nil {
fast = fast.next
}
if slow != nil {
slow = slow.next
}
counter++
}
return fast, slow
}
func (l *list) mergesort() {
// start with sublength of 1
// compare 0,with 1, 2 with 3
// skip n.next.next for next bunch
sublen := 1
len := 0
counted := false
for !counted || sublen < len {
for n := l.head; n != nil; {
fast, slow := skip(n, sublen)
merge(n, slow, sublen)
if !counted {
len += 2
}
n = fast
}
counted = true
sublen += sublen
}
}
func merge(p *node, q *node, len int) {
i := p
if q == nil {
// nothing to merge, return
return
}
j := q
ilen := 0
jlen := 0
var head *node
var prev *node
var end *node
var penult *node
for (i != q && ilen < len) && (j != nil && jlen < len) {
if i.val < j.val {
n := getNode(i.val)
append(n, &head, &prev)
i = i.next
penult = prev
prev = n
ilen++
} else {
n := getNode(j.val)
append(n, &head, &prev)
setEnd(&end, j, jlen, len)
j = j.next
penult = prev
prev = n
jlen++
}
}
for i != q && ilen < len {
n := getNode(i.val)
append(n, &head, &prev)
i = i.next
penult = prev
prev = n
ilen++
}
for j != nil && jlen < len {
n := getNode(j.val)
append(n, &head, &prev)
setEnd(&end, j, jlen, len)
j = j.next
penult = prev
prev = n
jlen++
}
// replace into original list
p.val = head.val
end.val = prev.val
// do we have any nodes between head and new end (prev) or is it just the
// two nodes (head and new end (prev)?
if head != penult {
p.next = head.next
penult.next = end
}
}
func setEnd(end **node, n *node, partlen int, len int) {
if n.next != nil && partlen < len-1 {
*end = n.next
} else {
*end = n
}
}
func append(n *node, head **node, prev **node) {
if *head == nil {
*head = n
*prev = n
} else {
(*prev).next = n
}
}
func main() {
l := newList([]int{10, 4, 2, 15, 8, 9, 12, 1, 6})
fmt.Println("Original: ")
printList(l.head)
l.mergesort()
fmt.Println("\nSorted:")
printList(l.head)
}
Also shared here
