単鎖表分かったか?

単鎖表は中点結点を求める.構想スピードポインタ

public ListNode getMid(ListNode left,ListNode right){
	ListNode slow = left;
	listNode fast= left;
	while(fast != right && fast.next != right){
		fast = fast.next;
		fast = fast.next;
		slow = slow.next;
	}
	return slow;
}

単鎖テーブルにリングがあるか否かを判定し、リングの入口点

を見つけ出す.

/*     */
public ListNode getEntrance(ListNode head){
	ListNode havecycle = getEncounter(head);
	if(havecycle != null){
		ListNode ptr1 = head;
		ListNode ptr2 = havecycle;
		while(ptr1 != ptr2){
			ptr1 = ptr1.next;
			ptr2 = ptr2.next;
		}
		return ptr1;
	}
	return null;
	
}
/*          null     */
public ListNode getEncounter(ListNode head){
	ListNode slow = head;
	ListNode fast = head;
	while(fast != null && fast.next != null){
		slow = slow.next;
		fast = fast.next;
		fast = fast.next;
		if(slow == fast){
			return slow;
		}
	}
	return null;
}