Oleksandr Gavenko's blog
2017-01-21 21:00 Find a loop in linked list

Today I'll show how to find a loop in linked list in linear time.

Assume that we have singly linked list:

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

To find loop in a list we will use two pointers that moves with different speed until they become equal or fast one become None. First incremented by one step, second incremented by two steps. They start from beginning of list with fast one step ahead.

If there is a loop with length len and loop begin from off offset at some step n we will have slow and fast pointer in same position:

slow: off + {(n - off) mod len}
fast: off + {(1 + 2*n - off) mod len}

or:

n - off = 1 + 2*n - off  (mod len)
1 + n = 0  (mod len)
n = len - 1  (mod len)

which will happen after len-1 or 2*len-1 or some X*len-1 step that should be greater then off.

Our lists may look like:

Node1 -> Node2 -> None

Node1 -> Node2 -> Node3 -> Node4
            ^                |
            |                |
            +----------------+

Solution is:

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

    def visual(self, depth):
        buf = []
        lst = self
        for _ in range(depth):
            buf.append(str(lst.value))
            lst = lst.next
            if not lst:
                break
        return " -> ".join(buf)

    def find_loop(self):
        slow = self
        fast = self.next
        steps = 0
        while fast is not None and fast.next is not None:
            print(slow.value, fast.value)
            if slow == fast:
                print("It takes: {} steps".format(steps))
                return True
            slow = slow.next
            fast = fast.next.next
            steps += 1
        return False

    def __repr__(self):
        if self.next:
            return "[List {} -> {} ->...]".format(self.value, self.next.value)
        else:
            return "[List {} -> None]".format(self.value)


def create_loop_list(loop_start, loop_len):
    lst_end = List(0)
    lst = lst_end
    for n in range(1, loop_len):
        lst = List(n, lst)
    lst_end.next = lst
    for n in range(loop_len, loop_len+loop_start):
        lst = List(n, lst)
    return lst

Output from running:

LST = create_loop_list(6, 3)
print(LST.visual(6+3+1))
print(LST.find_loop())

is:

8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 2
(8, 7)
(7, 5)
(6, 3)
(5, 1)
(4, 2)
(3, 0)
(2, 1)
(1, 2)
(0, 0)
It takes: 8 steps
True

From above formula it take 8 steps as a first number of 3*X - 1 form that bigger then 6 (this is happened when X=3).

interview, problem

Feeds

all / emacs / java / python

Tags

admin(1), anki(1), blog(1), css(2), cygwin(2), emacs(3), fs(1), git(1), hg(2), html(1), interview(11), java(2), js(3), lang(1), lighttpd(1), mobile(1), naming(1), printer(1), problem(5), quiz(6), rst(1), security(1), sql(1), srs(1), unit(1), utils(1), vcs(1), web(2), win(2)

Archive