Can you get the loop ?

[houjunchen]

You are given a node that is the beginning of a linked list. This list always contains a tail and a loop.

Your objective is to determine the length of the loop.

For example in the following picture, the tail's size is 3 and the loop size is 11.

給定一鏈結串列的起始節點，並保證該串列由一環形與一長條組成。

目標為決定此環形之長度。

以下圖為例，長條之長度為3且環形之長度為11。

http://www.codewars.com/kata/can-you-get-the-loop

[houjunchen]

Pass

[bucker]

Pass

[jawayang]

我看不懂這題目的意思...

[maoyang]

我看得懂, 給一個link list的起始節點, 判斷這個link list的組成會是一條線與一個環形, 算出這條線的長度與環形的長度, 但是我的問題是這個link list是要自己編嗎? 任意輸入一個link list的資料然後下去判斷與計算?

[jawayang]

有 link list 的範例? link list 長什麼樣子?

[houjunchen]

link list是題目給的，一開始會給一個起始節點，是那條線的最後一個點（以上圖來說就是最左上那個點）。總之題目給的起始節點一定可以讓你把全部的點都走過。

[houjunchen]

@jawayang 範例就是那張圖

[jawayang]

所以要寫出的答案就是算出 tail 跟 loop 的 size 嗎?

[houjunchen]

只要算出loop的size就好

[houjunchen]

我看得懂, 給一個link list的起始節點, 判斷這個link list的組成會是一條線與一個環形, 算出這條線的長度與環形的長度, 但是我的問題是這個link list是要自己編嗎? 任意輸入一個link list的資料然後下去判斷與計算?

@maoyang 題目給的link list一定是由一個tail與一個loop組成，他給的啟始點就是tail的最後一個點，從那個點開始走一定可以把全部的點都走過

[maoyang]

Pass

[jawayang]

Pass

[maoyang]

@houjunchen 更正一下, 後來我跟 @jawayang 討論結果, node應該是那條線(tail)的起始點, 不是最後一點

[maoyang]

@houjunchen 剛剛想一想, 不過就算是最後一點, 也是可以通過

[jawayang]

可以再試試看怎麼寫測試~

[houjunchen]

@maoyang 我們講的應該是同一個點，只是對tail的起始點的定義不一樣，所以我才在前面有補充

link list是題目給的，一開始會給一個起始節點，是那條線的最後一個點（以上圖來說就是最左上那個點）。

[vampireneo]

Pass

[vicky-sunshine]

我想詢問一下大家這題都是怎麼寫測試的？ 他提供的測試似乎不太完整 想參考一下

[jawayang]

我想說做法應該是要先寫一個nodes產生器 然後再去做驗證的動作？ 例如 genNodes(3,11); 然後就會產生 tail 3 cycle 11 的 nodes 然後期望值就是 11

[vampireneo]

其實我本來沒有自己寫測試, 只直接 submit 來當測試 :P 真的要寫的話, 就只好先寫個 nodes 產生器了...

var Node = function () {
  this.next = null;
  this.getNext = function() {
    return next;
  };
};

function genNodes(tail, loop) {
  let last = null;
  let total = tail + loop;
  let loopNode = null;
  let firstNode = null;
  while(total-- > 0) {
    var n = new Node();
    if (total + 1 === tail + loop)
      firstNode = n;
    if (total === loop - 1)
      loopNode = n;
    if (last !== null) last.next = n;
    last = n;
  }
  n.next = loopNode;
  return firstNode;
}

describe("Solution", function(){
  it("should test for something", function(){
    Test.assertEquals(loop_size(genNodes(3,11)), 11);
    Test.assertEquals(loop_size(genNodes(0,2)), 2);
    Test.assertEquals(loop_size(genNodes(8,1)), 1);
    Test.assertEquals(loop_size(genNodes(1000,31)), 31);
  });
});