{"id":134,"date":"2013-08-29T15:35:33","date_gmt":"2013-08-29T22:35:33","guid":{"rendered":"http:\/\/samueldotj.com\/blog\/?p=134"},"modified":"2013-08-29T15:35:33","modified_gmt":"2013-08-29T22:35:33","slug":"fix-loop-in-a-linked-list","status":"publish","type":"post","link":"http:\/\/samueldotj.com\/blog\/fix-loop-in-a-linked-list\/","title":{"rendered":"Fix loop in a linked list"},"content":{"rendered":"

Cycle or loop in a linked list with \"n\" nodes is shown in pictorial representation.
\n

\"Loop<\/a>

Loop in a singly linked list<\/p><\/div><\/p>\n

In this picture the number of nodes in the list is \"n\" and the last node points to node at a position x(which created the cycle). From the picture it is obvious that to fix the loop:<\/p>\n

    \n
  1. Find the last element<\/li>\n
  2. Correct it to point end(NULL)<\/li>\n<\/ol>\n

    In the above steps, step 1(find the last element) is little difficult if total number of nodes in the list is unknown<\/strong>. In this post I will describe a method I discovered to find the last node. I drew couple of pictures to explain the complexity of the problem. The following pictures explains the same loop condition but in different form. It explains why it is hard to find the last node.
    \n    \"Cycle2\"<\/a><\/p>\n

    \"Cycle3\"<\/a>
    \nThe illustration also tells us the following
    \n\"n = x+y\"
    \nwhere
    \n  \"n\" is total number of nodes in the list
    \n  \"x\" is number of nodes before the cycle starts.
    \n  \"y\" is number of nodes forming the cycle.<\/p>\n

    If we have value of \"x\" and \"y\" then the equation can be solved, which will give the last node\u2019s location.<\/p>\n

    Finding \"y\"<\/strong><\/p>\n

      \n
    1. Detect the cycle using Floyd\u2019s Cycle detection algorithm. (Two pointer with varying speed)<\/li>\n
    2. When cycle is detected\n
        \n
      1. Store the current node as H<\/li>\n
      2. Move to next node and increment y(y++)<\/li>\n
      3. If current node is H then exit<\/li>\n
      4. Goto step 2<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

        Finding \"x\"<\/strong>
        \nLet\u2019s first see the easiest way to solve this:<\/p>\n

          \n
        1. Have two pointers (p1, p2)<\/li>\n
        2. p1 = node 0<\/li>\n
        3. p2 = p1 + y nodes<\/li>\n
        4. if p1 == p2 then we found the result is \"x = p1\"<\/li>\n
        5. p1 = p1 + y nodes<\/li>\n
        6. goto step 3.<\/li>\n<\/ol>\n

          The complexity of this algorithm linear depends on \"x\". For example if \"x\" is 10K and \"y\" is 2 then number of node visits are > 20K. In other words the complexity is \"O(2x + y)\".<\/p>\n

          I believe it can be done in \"O(n)\" or \"O(x + y)\" with following method This following diagram captures state when the “tortoise and the hare” algorithm detects the cycle.
          \n          \"CycleFix\"<\/a><\/p>\n

          Lets define few more variables at the time of cycle detection:
          \n\"T\" is the total number of nodes tortoise traveled.
          \n\"H\" is the total number of nodes hare traveled.
          \n\"r\" can be defined as number of nodes before the ‘last node’<\/p>\n

          \"T = 2H \newline
          \nwhere c is the number of complete cycles hare covered.
          \n\"T > H \newline
          \nFrom this we can derive
          \n\"c = H / y + 1\"<\/p>\n

          Using value of \"c\", \"r\" can be derived.
          \n\"x + y - r = H \newline<\/p>\n

          Using this formula \"r\" can be found. With this \"r\" value, the last node can be found by travelling \"r-1\" nodes where T and H met.<\/p>\n","protected":false},"excerpt":{"rendered":"

          Cycle or loop in a linked list with nodes is shown in pictorial representation. In this picture the number of nodes in the list is and the last node points to node at a position x(which created the cycle). From the picture it is obvious that to fix the loop: Find the last element Correct […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-134","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts\/134","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/comments?post=134"}],"version-history":[{"count":10,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts\/134\/revisions"}],"predecessor-version":[{"id":177,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts\/134\/revisions\/177"}],"wp:attachment":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/media?parent=134"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/categories?post=134"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/tags?post=134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}