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 with a linear time complexity.

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 becomes None. First is incremented by one step, second is incremented by two steps. They start from the beginning of a list with the fast one step ahead.

If there is a loop with length len and loop begins from off offset at some step n we will have slow and fast pointer in the 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 is 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 takes 8 steps as the first number in form of 3*X - 1 that is bigger than 6 (this is happened when X=3).

interview, problem

Feeds

all / emacs / java

Tags

adb(1), admin(1), android(1), anki(1), ansible(2), aop(1), blog(2), bytecode(1), c(1), css(2), cygwin(2), driver(1), emacs(3), fs(1), git(3), google(1), gradle(1), hardware(1), hg(2), html(1), interview(13), java(4), js(3), lang(2), lighttpd(1), markdown(1), mobile(1), naming(1), oracle(1), print(1), problem(5), python(1), quiz(6), rst(2), security(3), spring(2), sql(2), srs(1), style(1), tls(2), txt(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)

Archive