/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    mid := getMid(head)

    l, r := head, reverse(mid)
    
    for l != nil && r != nil {
        if l.Val != r.Val {
            return false
        }

        l = l.Next
        r = r.Next
    }

    return true
}

func getMid(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func reverse(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    return prev
}

func removeDuplicates(nums []int) int {
    slow, fast := 1, 1
    for fast < len(nums) {
        if nums[fast] == nums[fast-1] {
            fast++
            continue
        }

        nums[slow] = nums[fast]
        slow++
        fast++
    }
    return slow
}

func removeDuplicates(nums []int) int {
    slow, fast := 0, 0
    for fast < len(nums) {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }

        fast++
    }

    return slow+1
}

func removeElement(nums []int, val int) int {
    slow, fast := 0, 0
    for fast < len(nums) {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
        fast++
    }
    return slow
}

func twoSum(nums []int, target int) []int {
    l, r := 0, len(nums)-1
    for l < r {
        v := nums[l] + nums[r]

        switch {
            case v == target:
                return []int{l+1, r+1}
            case v < target:
                l++
            default:
                r--
        }
    }
    
    panic("impossible")
}

func reverseString(s []byte)  {
    i, j := 0, len(s)-1
    for i < j {
        s[i], s[j] = s[j], s[i]
        i++
        j--
    }
}

func longestPalindrome(s string) string {
    lp := ""

    for i := range s {
        ss := palindrome(s, i, i)
        if len(ss) > len(lp) {
            lp = ss
        }

        if i > 0 {
            ss := palindrome(s, i-1, i)
            if len(ss) > len(lp) {
                lp = ss
            }
        }
    }

    return lp
}

func palindrome(s string, i, j int) string {
    l, r := i, j
    for l >= 0 && r < len(s) && s[l] == s[r] {
        l--
        r++
    }
    return s[l+1:r]
}

func removeDuplicates(nums []int) int {
    slow, fast := 0, 0
    for fast < len(nums) {
        // fmt.Printf("slow = %d, fast = %d | %v | %v\n",
        //     slow, fast, nums[:slow], nums,
        // )
        if  slow-2 < 0 || nums[fast] != nums[slow-1] || nums[fast] != nums[slow-2] {
            // new element
            nums[slow] = nums[fast]
            slow++
        } 
        
        fast++
    }

    return slow
}