leetcode day 13: linked list loop

Given a linked list, determine if it has a loop.

I started out with the simplest possible thing that could work: when looking to see if you have more than N of a thing, use a map.

**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    seen := make(map[*ListNode]bool)
    for scan := head; scan != nil; scan = scan.Next{
         _, ok := seen[scan] 
         if ok {
            return true
        }
        seen[scan] = true
    }
    return false
}

Small, simple, but not very fast. 14th percentile in speed, 8th percentile in memory.

I vaguely remembered that there was a pointer-chasing way to do this, and that’s the fast and small way. (This falls into the “do you know the trick” category, which I kinda hate.)

func hasCycle(head *ListNode) bool {
    slow := head
    fast := slow
    
    if head == nil {
        return false
    }
    
    for {
        // if we'd run off the end, stop.
        if slow.Next == nil || fast.Next == nil || fast.Next.Next == nil {
            return false
        }

        slow = slow.Next
        fast = fast.Next.Next

        if fast == slow {
            return true
        }
    }
    return false
}

Considerably faster: 95th percentile in speed, 45th in memory, which is interesting.

Now we start getting into “I would fire you if you did this” solutions.

How about if we just overwrite the value with an impossible one, and if we see the impossible value, return true (because it couldn’t be there unless we put it there)? It’s slower, which is to be expected, since we’re modifying the nodes and looking at them, not just looking at pointers. But surprisingly, the memory usage is still around 43%. And the list contents are trashed.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
const invalidValue = 99999999

func hasCycle(head *ListNode) bool {
    // Destructive version.
    scan := head
    
    if head == nil {
        return false
    }
    
    for {
        // if we'd run off the end, stop.
        if scan.Next == nil {
            return false
        }
        if scan.Val == invalidValue {
            return true
        }
        scan.Val = invalidValue

        scan = scan.Next
    }
    return false
}

So what gets us better memory usage? How about breaking the links, and pointing them to na-na land, and stopping if we get a pointer to na-na land?

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func hasCycle(head *ListNode) bool {
    // Another destructive version.
    scan := head
    
    // Create an off-in-nowhere node.
    tumbolia := &ListNode{9999999, nil}
    
    if head == nil {
        return false
    }
    
    for {
        if scan == tumbolia {
            // we're in na-na land
            return true
        }

        // if we'd run off the end, stop.
        if scan.Next == nil {
            return false
        }

        // point the next of this node to na-na land.
        here := scan
        scan = scan.Next
        here.Next = tumbolia
    }
    return false
}

No major improvement. 90th percentile in speed, 43rd percentile in memory. List structure is trashed.

So overall, the Floyd two-pointer is the winner; would love to see something that uses less memory, but haven’t found anything yet.