sasbury.com

Talking to some folks the other day a couple of fun problems came up:

• How do you find cycles in a linked list?
• How do you reverse a linked list?

Both of these algorithms can be implemented with very little extra memory, and I thought it would be fun to build them in Go. The full solutions can be found on github.

For this code we will use a simple Node type that holds an integer value so that we can create "ordered" lists.

type Node struct {
    value int
    next  *Node
}

Finding Cycles in a Linked List

Finding cycles in a linked list relies on two simple ideas. First, if you have a cycle in a linked list it has to be the end of the list. Second, if you walk two cursors around a circle of linked list nodes, at different speeds, eventually they will end up on the same node. In other words. if you start at the begining of a list and start walking one cursor one node at a time, and another cursor two nodes at a time, when they hit the loop the faster cursor will eventually catch the slower cursor and you will be able to identify the cycle.

For a slow cursor we will use a function that moves forward one step when called:

func slowStep(n *Node) *Node {
    return n.next
}

For the fast cursor we will move forward two steps when called:

func fastStep(n *Node) *Node {
    n = n.next

    if n != nil {
        n = n.next
    }

    return n
}

In Go this algorithm looks like this:

func FindCycle(head *Node) bool {

    if head == nil {
        return false
    }

    slowWalker := slowStep(head)
    fastWalker := fastStep(head)

    for slowWalker != nil && fastWalker != nil {

        if slowWalker == fastWalker {
            return true
        }

        slowWalker = slowStep(slowWalker)
        fastWalker = fastStep(fastWalker)
    }

    return false
}

So we start at the head, and move forward immediately. This could result in getting to the end of a short list, which is fine. Then we continue to move forward, checking each time if we have found a cycle.

To test this code, I created a function to build an ordered linked list of arbitrary length. Using those lists, I created a few different test scenarios:

func TestNoCycle(t *testing.T) {
    for i := 0; i < NUM_TESTS; i = i + 1 {
        head, _ := BuildList(i)
        assert.False(t, FindCycle(head))
    }
}

func TestFullCycle(t *testing.T) {
    for i := 1; i < NUM_TESTS; i = i + 1 {
        head, tail := BuildList(i)
        tail.next = head
        assert.True(t, FindCycle(head))
    }
}

func TestCycleWithPrefix(t *testing.T) {
    for i := 1; i < NUM_TESTS; i = i + 1 {
        head, tail := BuildList(i)
        cycleHead, cycleTail := BuildList(i)
        tail.next = cycleHead
        cycleTail.next = tail
        assert.True(t, FindCycle(head), fmt.Sprintf("There should be a cycle of %d", i))
    }
}

and run the scenarios for various size lists, from 0 or 1 to 1000.

What is great about this algorithm is that it uses almost no additional memory, just the two cursors. It does take time, as in the degenerate cases it might take a couple loops around the cycle to get the cursors to match up.

You can read more about Floyd's cycle-finding algorithm on wikipedia.

Reversing a Linked List

Reversing a linked list is a bit easier. Of course you could do this by creating a stack or array or some other data structure, but it is possible to reverse the list in place with just a couple extra pieces of data.

func Reverse(head *Node) *Node {

    h := head
    n := head.next
    h.next = nil

    for n != nil {
        newN := n.next
        n.next = h
        h = n
        n = newN
    }

    return h
}

First, you have to keep track of the new head. This is the node we will return as the new head of the linked list. Second, we keep track of the next element in the list. When that next element is nil, we are at the end of the list. Finally, we use a temporary variable to keep track of the "next next" element. This variable peeks ahead and lets us move the head forward while reversing its next to point backwards.

In order to test my Reverse function I wrote a couple of utilities that check if the list passed to them is increasing or decreasing, using the integer values. Then I try reversing an increasing list and make sure I get a decreasing list.

func TestReverse(t *testing.T) {
    for i := 1; i < NUM_TESTS; i = i + 1 {
        head, tail := BuildList(i)

        assert.True(t, Increasing(head))

        reversed := Reverse(head)

        assert.Nil(t, head.next)
        assert.Equal(t, reversed.value, tail.value)
        assert.True(t, Decreasing(reversed))

        if i != 1 {
            assert.NotNil(t, tail.next)
        }
    }
}

Again I am performing the test on a 1000 different list links.

algorithms programming go