2
$\begingroup$

Finding a loop in a linked list is a classic algorithm but I found an off-by one case that is making me question my sanity, this first solution works:

def findLoop(head):
    def p(s, f):
        print(f'slow: {s.value}, fast: {f.value}')
        
    slow = head.next
    fast = head.next.next
    
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next.next

    p(slow, fast)
    slow = head
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next 
    return slow

This second one goes into an infinite loop since on the second while loop, the pointers never meet:

def findLoop(head):
    def p(s, f):
        print(f'slow: {s.value}, fast: {f.value}')
        
    slow = head
    fast = head.next
    
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next.next

    p(slow, fast)
    slow = head
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next 
    return slow

Note that all that changed is the starting conditions: in the working solution we have slow = head.next; fast = head.next.next; while in the breaking solution we have: slow = head; fast = head.next. This change should not have a breaking effect and even though I can walk through it by had, I don't understand why it should happen, given that we only shift the starting conditions by one.

Supplementary Material

Ready to run example for experimenting:

class LinkedList:
    def __init__(self, value):
        self.value = value
        self.next = None

def findLoop(head):
    def p(s, f):
        print(f'slow: {s.value}, fast: {f.value}')
        
    slow = head.next
    fast = head.next.next
    
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next.next

    p(slow, fast)
    slow = head
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next 
    return slow
    
case =  [
      {"id": "0", "next": "1", "value": 0},
      {"id": "1", "next": "2", "value": 1},
      {"id": "2", "next": "3", "value": 2},
      {"id": "3", "next": "4", "value": 3},
      {"id": "4", "next": "5", "value": 4},
      {"id": "5", "next": "6", "value": 5},
      {"id": "6", "next": "7", "value": 6},
      {"id": "7", "next": "8", "value": 7},
      {"id": "8", "next": "9", "value": 8},
      {"id": "9", "next": "4", "value": 9}
    ]

def create(case):
    for c in case:
        c['node'] = LinkedList(c['value'])
    for c in case:
        c['node'].next = case[int(c['next'])]['node']     
    return case[0]['node']

def test():
    head = create(case)
    findLoop(head)

test()
    
$\endgroup$
1
  • 2
    $\begingroup$ When you say it "should not have a breaking effect", I suggest you take this as an indication that your intuition about what should and shouldn't matter isn't 100% correct in this situation. You already know of a counterexample, which already demonstrates that one version doesn't work, so it's not clear what kind of "why" answer you're hoping for. Have you tried constructing a proof of correctness for the correct algorithm, then seeing what breaks down when you try to apply it to the wrong algorithm? That is sometimes one helpful way to get a better sense of "why" it fails. $\endgroup$
    – D.W.
    Jan 4 at 0:22
2
$\begingroup$

I am delighted to see another example of the infamous off-by-one error.


"All that changed is the starting conditions". "This change should not have a breaking effect" since "we only shift the starting conditions by one." Well, as D.W. implied in his comment, that change does have a breaking effect!

With that shifting change, the node where slow and fast meet at the end of first while in the right version of findLoop is not the same as that in the wrong version of findLoop. In fact, they meet one node earlier in the wrong version than in the correction version. That means, the distance between head and fast at the end of the first while in the wrong version is one less than that distance in the right version. Since slow is reset to head before the start of the second while in both version, the distance between slow and fast at the start of the second while in the wrong version is one less than that distance in the right version.

For the second while to end, the distance between slow and fast must be a multiple of the period of the loop of the linked list. So the second while will go forever in the wrong version of findLoop, as long as the period is not $1$.


Exercise (easy): Assume that there is a loop in the linked list and that head.next != head.next.next. Explain why the node where slow and fast meet at the end of first while in the wrong version of findLoop is one node earlier than that node in the correction version, i.e. the next node of the former node is the latter node.

$\endgroup$
1
  • $\begingroup$ > "For the second while loop to end, the distance between slow and fast must be a multiple of the period" -- this is warm enough for me to look into and appreciate. Thank you very much. $\endgroup$ Jan 4 at 3:35

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.