876 - Middle of the Linked List

解法一 - Fast & Slow Pointer

這題也還滿單純的,我們可以用兩個 pointer,fast 一次走兩步,slow 一次走一步,當 fast 走到底的時候,slow 就會在中間。

不過我們還需要注意一下,linked list 長度有 even 跟 odd 兩種,以下分別解析:

  • Odd:

      1->2->3->NULL
    

    當 slow 走到 2,fast 已經走到 3,下一次不會再進 while 迴圈,這時 return slow 就好。

  • Even:

      1->2->3->4->NULL
    

    當 slow 走到 2,fast 走到 3,下一次因為 fast->next->next 就是 NULL 了,所以不會再進 while 迴圈,但這時要 return slow->next。

實作如下:

/**
 * 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* slow = head;
        ListNode* fast = head;

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

        if(fast->next == NULL) return slow;
        else return slow->next;
    }
};

results matching ""

    No results matching ""