Middle Element Of Linked List | Linked List | Data Structure

CODE:

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
       ListNode* middleNode(ListNode* head) {
             ListNode * fast = head;
             ListNode * slow = head;

             while(fast != nullptr && fast->next != nullptr){
                   fast = (fast->next)->next;
                   slow = slow->next;
             }

             return slow;
             }
};

EXPLANATION:

Input: [1,2,3,4,5]
Output: Node 3
Input: [1,2,3,4,5,6]
Output: Node 4
 
The slow pointer iterates at half the index of the fast pointer.

Hence, when the fast pointer reaches the end of the linked list, the slow pointer is pointing to the middle element of the linked list.

Leave a Reply

Your email address will not be published. Required fields are marked *