快慢指針取連結清單中間值

先随機生成一個長度20以内的連結清單（頭插法），

然後列印該連結清單（周遊）。

取中值：快慢指針法。

定義兩個連結清單節點，讓其從連結清單頭部以不同速度向後滑動，快指針是慢指針的兩倍速度。

當快指針到達連結清單尾部時，慢指針剛好指向中間位置。

package com.yc.myHibernate;

import java.util.Random;

/**
 * 快慢指針取對外連結表中間的值
 * @author yc
 *
 */
public class Solution {

	public static void main(String[] args) {
		ListNode head = creatListNode();
		printListNode(head);
		getMidList(head);
	}
	
	/**
	 * 生成一個随機長度的連結清單
	 * @return
	 */
	private static ListNode creatListNode() {
		//生成随機長度
		Random random = new Random();
		ListNode head = new ListNode();
		for (int i = 0; i < random.nextInt(20) + 1; i++) {
			ListNode node = new ListNode();
			node.value = i;
			node.next = head.next;
			head.next = node;
		}
		//去掉頭節點，傳回第一個有效節點
		return head.next;
	}
	
	/**
	 * 列印連結清單
	 * @param head
	 */
	private static void printListNode(ListNode head) {
		while (head != null) {
			System.out.print(head.value);
			head = head.next;
		}
		System.out.println();
	}
	
	/**
	 * 快慢指針取連結清單中值，時間複雜度O(1/2)
	 * @param head
	 */
	public static void getMidList(ListNode head) {
		ListNode fastList = head;
		
		while (fastList.next != null) {
			if (fastList.next.next != null) {				
				head = head.next;
				fastList = fastList.next.next;
			} else {
				//若連結清單長度為偶數，則輸出最中間兩個值。
				fastList = fastList.next;
				System.out.println("中值 : " + head.next.value);
			}
		}
		System.out.println("中值： " + head.value);
	}
}

class ListNode{
	int value;
	ListNode next;
	
	public ListNode() {
	}
}