tags: leetcode easy Linked List Two Pointers

876. Middle of the Linked List

Description

Given the head of a singly linked list, return the middle node of the linked list.

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

Examples

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

• The number of nodes in the list is in the range [1, 100].
• $1 \leq Node.val \leq 100$ .

Code

• Way 1 :

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *fast, *slow;
    for(fast = head, slow = head;;){
        // Wether we can jump to the next node
        if(fast->next != NULL){
            // Whether we can jump two nodes?If we can, jump and set slow pointer
            if((fast->next)->next != NULL){
                fast = (fast->next)->next;
                slow = slow->next;
            }
            // If we can only jump ome node, it means the link-list has even nodes and slow is the first middle
            else
                return slow->next;
        }
        // If we can not jump to the next node, it means we have odd nodes and slow is the middle
        else
            return slow;
    }
}

• Way 2 :

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    int count;
    struct ListNode *tmp;
    for(count = 0, tmp = head ; tmp ; count++)
        tmp = tmp->next;
    count /= 2;
    for(int i = 0 ; i < count ; i++)
        head = head->next;
    return head;
}

Complexity

• Way 1 & 2:

Space	Time
$O(1)$	$O(N)$

Result

• Way 1 :
  • Runtime: 4 ms, faster than 32.41%
  • Memory Usage: 6 MB, less than 7.74%
• Way 2 :
  • Runtime: 0 ms, faster than 100.00%
  • Memory Usage: 5.9 MB, less than 52.55%