Leetcode#876 Middle of the Linked List－大家一起學AI

該題Leetcode Middle of the Linked List為實現得到一半以後的鏈結串列，如以下所示，範例1共有5個鏈結串列節點(1、2、3、4、5)，要取得中間以後的數量為3個，即輸出3、4、5，而範例2共有6個鏈結串列節點(1、2、3、4、5、6)，要取得中間以後的數量為3個，即輸出4、5、6。

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.

作法解析:第一個while迴圈加總出該鏈結串列共有幾個節點，並將全部節點數除2，第二個while再移動counter之次數，即可得到後半段的鏈結串列。

程式碼:

/**
 * 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 *p = head;
        int counter = 0;       
        
        while(p != NULL)
        {
            p = p->next;
            counter++;
        }       
        
        counter /= 2;      
        
        while(counter-- > 0)
        {
            head = head->next;
        }
             
        return head;
    }
};

1.第一個while迴圈，透過移動指標p計算鏈結串列總數(counter)。

2.取得中間數量後，透過第二個while迴圈移動head指標的位置，即可得到一半鏈結串列的結果(移動後即看不到前面鏈結串列節點)。