Middle of Linked List

Find the middle node of a linked list.

Example

Given 1->2->3, return the node with value 2.

Given 1->2, return the node with value 1.

1 value 1

1->2 value1

1->2->3 value 2

1->2->3->4 value 2

1->2->3->4->5 value 3

...

/**

* Definition for ListNode

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

*/

public class Solution {

/**

* @param head: the head of linked list.

* @return: a middle node of the linked list

*/

public ListNode middleNode(ListNode head) {

// Write your code here

ListNode slow = head, fast = head;

while (fast != null && fast.next != null && fast.next.next != null) {

slow = slow.next;

fast = fast.next.next;

}

return slow;

}