4
\$\begingroup\$

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

Jamal
35.2k13 gold badges134 silver badges238 bronze badges
asked Aug 10, 2015 at 19:52
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please add a language tag \$\endgroup\$ Commented Aug 11, 2015 at 6:01
  • \$\begingroup\$ You already state that the code is in Go, so there's no reason to remove this tag. A language tag is required. \$\endgroup\$ Commented Aug 11, 2015 at 6:12

1 Answer 1

2
\$\begingroup\$

Just some random notes:

l := new(list)
l.head = getNode(arr[0])

This is usually spelled l := &list{head: getNode(arr[0])}.

n := new(node)
n.val = v

Again, can be shortened to n := &node{val: v}.

var head *node
var prev *node
var end *node
var penult *node

Shorten to var head, prev, end, penult *node.

func append

This is a very bad name for a function because it clashes with a built-in. Better change to something like appendList or make it a method.

answered Aug 11, 2015 at 11:58
\$\endgroup\$
2
  • \$\begingroup\$ Thank you, can also please add your review comments about the algo ? \$\endgroup\$ Commented Aug 12, 2015 at 17:59
  • \$\begingroup\$ Looks fine to me although sorting algorithms aren't really one of my strengths. \$\endgroup\$ Commented Aug 14, 2015 at 12:08

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.