/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let mark = 0;
    let index = 0;
    while (index < nums.length) {
        if (mark === 0) {
            mark++
            index++
        } else if (mark === 1) {
            if (nums[index] !== nums[index - 1]) {
                mark = 0
            } else {
                mark++
                index++
            }
        } else {
            if (nums[index] !== nums[index - 1]) {
                mark = 0
            } else {
                nums.splice(index, 1)
            }
        }
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let left = 0
    let right = 1
    while (right < nums.length) {
        if (nums[right] === nums[left] && right - left < 2) {
            right++
        } else if (nums[right] === nums[left]) {
            nums.splice(right, 1)
        } else {
            left = right
            right++
        }
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    nums.sort()
    let index = 0
    let mark = 1
    while (index < nums.length && mark < nums.length / 2) {
        if (nums[index] === nums[index + 1]) {
            mark++
        } else {
            mark = 1
        }
        index++
    }
    return nums[index]
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let index = 1
    let value = nums[0]
    let count = 1
    while (index < nums.length) {
        if (count === 0) {
            value = nums[index]
        }
        if (nums[index] === value) {
            count++
        } else {
            count--
        }
        index++
    }
    return value
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    Array.from({ length: k % nums.length }, () => nums.unshift(nums.pop()))
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let profit = 0
    for (let i = 0; i < prices.length - 1; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[j] - prices[i] > profit) {
                profit = prices[j] - prices[i]
            }
        }
    }
    return profit
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0
    let minPrice = prices[0]

    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i]
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice
        }
    }
    return maxProfit
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    const regex = /[^a-z0-9]/gi
    s = s.replace(regex, '').toLowerCase()
    for (let i = 0; i < s.length / 2; i++) {
        if (s[i] !== s[s.length - 1 - i]) {
            return false
        }
    }
    return true
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    const map = new Map()
    while (head !== null) {
        if (map.has(head)) {
            return true
        }
        map.set(head)
        head = head.next
    }
    return false
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null || head.next === null) {
        return false
    }
    let slow = head
    let fast = head.next
    while (slow !== fast) {
        if (fast === null || fast.next === null) {
            return false
        }
        slow = slow.next
        fast = fast.next.next
    }

    return true
};