3
\$\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

\$\endgroup\$
  • 1
    \$\begingroup\$ Please add a language tag \$\endgroup\$ – Heslacher Aug 11 '15 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\$ – Jamal Aug 11 '15 at 6:12
1
\$\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.

\$\endgroup\$
  • \$\begingroup\$ Thank you, can also please add your review comments about the algo ? \$\endgroup\$ – nmdr Aug 12 '15 at 17:59
  • \$\begingroup\$ Looks fine to me although sorting algorithms aren't really one of my strengths. \$\endgroup\$ – Ainar-G Aug 14 '15 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.