2.6 -- find the first node of a circular linked list

Q：
Given a circular linked list, implement an algorithm which returns the node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points
to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A - > B - > C - > D - > E - > C [the same C as earlier]
Output: C

首先，我们先make circular.(for simplicity，没有边界检查什么的)

 public static void makecircular(LinkList list1, int ithPosition) {
  // making the list1 as circular , by putting the last one's next to the i_th postion
  Node ithNode = null;
  Node runner = list1.header;
  int cound = 0;
  while(runner.next!=null){
   cound++;
   if(cound == ithPosition){
    ithNode = runner;
   }
   runner = runner.next;
  }
  runner.next = ithNode;
 }

A：
 最SB 的方法，就是将map every object into a hash table, and if exist, check whether they are exactly the same. ------但如何保证对象的hash也没有重复呢？？？

用两个指针， 或者说，是两个runner，一快一慢，走阿走，直到快的，追上慢的。（可是这样只能说明有loop. ---- 慢的一次走一步，快的一次走2步)
再一个SB的算法，就是 从头儿一个个得删除节点，然后，看是否还有回路。
呵呵，先用SB的算法做吧。

自己写的算法，比较SB， 而且，结果也不全对，还是不写在这儿了。肏，浪费了好几个小时。



第二种方法，就是书上的解释。
fast runner一次跑2个节点。
slow runner一次跑1个节点。
第一次相遇后，fast runner的速度降为1，并回到header所指向的起始位置。，slow runner继续跑。直到再次相遇的时候，就为第一个节点。
自己的证明如下。

代码如下：

	private static Node findFirstOfLoop(LinkList list) {
		Node slowRunner = list.header.next;
		Node fastRunner = null;
		if (slowRunner != null) {
			fastRunner = slowRunner.next;
		}
		// find the first meet, record its position
		while (slowRunner != fastRunner) {
			if (fastRunner == null || fastRunner.next == null) {
				// we find that the list do not contains loop
				return null;
			}
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next.next;
		}
		// Now they are the same, we reset the fastRunner at the beginning, and
		// run again
		fastRunner = list.header.next;
		slowRunner = slowRunner.next;
		while (slowRunner != fastRunner) {
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next;
		}
		return slowRunner;

	}

Mistakes：
1： 在方法中， i 应该每次增加的，可是为什么没有增加呢？
     static void printList(LinkList list, int maxNumElements) {
      
        Node node = list.header.next;
        int i =0;
        while (node != null && i<maxNumElements) {
            System.out.print(node.data + "\t");
            node = node.next;
            i=i+1;
        }
        System.out.println();
    }

运行时，i的值，一直是0. 而如果变成i = i+1 就可以了。为什么呢？ Learned: 1: java中， constructor call constructor

class AA { 
    private String a;
    private String b;
 
    public AA(String a){ 
        this.a = a;
    } 
   
    public AA(String a, String b){ 
        this(a);
        this.b = b;
    } 
}

2:在 circular list中， 仅仅delete 指向的一个节点，是并不能真正删除的， 要考虑是否因为是circluar的，所以，被略过的object，依然还存在。

3：  看下面的一段代码，

		// Now they are the same, we reset the fastRunner at the beginning, and
		// run again
		fastRunner = list.header.next;
		while (slowRunner != fastRunner) {
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next;
		}

仅仅这样的话，slowRunner 和fastRunner会相差一个的距离。-------->而再上图的证明中，第一次相遇后，fastRunner要回到队列的首位置，   而  slowRunner是要走到下一个的。