876. Middle of the Linked List

2018-08-04

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge’s serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

The number of nodes in the given list will be between 1 and 100.

code:

I create 2 pointers which are ‘fast’ and ‘slow’. fast pointer goes 2 time faster then slow, so that when fast pointer reaches to the end, we can see the slow pointer is at middle of the linked list.

depends on fast pointer is at the end of the list or 2 node away from the end. I return either slow.next or slow for the answer.

public class Solution {
    public ListNode MiddleNode(ListNode head) {
        var result =  new ListNode(0);
        var fast = head;
        var slow = head;
        while(fast.next != null && fast.next.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }   
        if(fast.next != null)
            result.next = slow.next;
        else
            result.next = slow;
        return result.next;
    }
}