leetcode解題：(Easy) 876. Middle of the Linked List

題目：https://leetcode.com/problems/middle-of-the-linked-list/

描述：給定一個鏈結串列，回傳鏈結串列最中間的node，如果有2個最中間的node則回傳其中第2個node

解題思路：用2個前進速度分別為1步跟2步的node遍歷鏈結串列，當走的快的到達尾端時走的慢的就會正好在中間位置

程式碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode mid = head;
        head = head.next;
        while(head != null) {
            mid = mid.next;
            head = head.next == null ? head.next : head.next.next;
        }

        return mid;
    }
}

時間複雜度：O(n)
空間複雜度：O(1)

tags: leetcode easy linked list two pointer