Mercurial > blog
changeset 155:158ded42355d
Fixed grammar.
author | Oleksandr Gavenko <gavenkoa@gmail.com> |
---|---|
date | Tue, 30 Oct 2018 19:18:51 +0200 |
parents | cce2393efbe3 |
children | b6f9e1fd2c30 |
files | bd51fb68-e005-11e6-8ee5-485b39c42d0f/index.rst |
diffstat | 1 files changed, 9 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- a/bd51fb68-e005-11e6-8ee5-485b39c42d0f/index.rst Tue Oct 30 19:13:58 2018 +0200 +++ b/bd51fb68-e005-11e6-8ee5-485b39c42d0f/index.rst Tue Oct 30 19:18:51 2018 +0200 @@ -6,7 +6,7 @@ :updated: 2017-01-21 :tags: interview, problem -Today I'll show how to find a loop in linked list in linear time. +Today I'll show how to find a loop in linked list with a linear time complexity. Assume that we have singly linked list:: @@ -16,11 +16,11 @@ 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. +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 begin from ``off`` offset at some step ``n`` we will -have slow and fast pointer in same position:: +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} @@ -31,8 +31,8 @@ 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``. +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:: @@ -112,6 +112,6 @@ 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``). +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``).