LeetCode - 876. Middle of the Linked List

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.

 

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 <= Node.val <= 100

Method 1 : Two Pointer Solution

struct ListNode* middleNode(struct ListNode* head){
    if(head == NULL) return head;
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
        
    return slow;
}

Method 2 : By Counting Total Nodes

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *tmp = head;
    int cnt =0;
    while(tmp->next !=NULL) {
        cnt++;
        tmp = tmp->next;
    }
    cnt++;
    tmp = head;
    for(int i = 0; i < cnt/2; i++) {
        tmp = tmp->next;
    }       
        
    return tmp;
}

2번 방법에서, list 갯수 count 할때, head 다음부터하는거라, list 갯수가 ... 5개면 count 는 4로 나온다.

그러면 count 값을 첨부터 1로 초기화 하던지 아님 나중에 1을 더해주던지 해야하는 것이다.

난 2번 방법으로 풀었는데, 1번 방법도 유명한가부당... ^^ 허허 ㅠㅅㅠ 이런 쥐니어스들....