class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = null, nodeOne = dummy, nodeTwo = null;
        while (nodeOne.next != null && nodeOne.next.next != null) {
            prev = nodeOne;
            nodeOne = prev.next;
            nodeTwo = prev.next.next;
            nodeOne.next = nodeTwo.next;
            nodeTwo.next = nodeOne;
            prev.next = nodeTwo;
        }
        return dummy.next;
    }
}

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        helper(ans, new StringBuilder(), n, n);
        return ans;
    }

    private void helper(List<String> ans, StringBuilder currString, int openLeft, int closedLeft) {
        if (openLeft == 0 && closedLeft == 0) {
            ans.add(currString.toString());
            return;
        }
        if (openLeft > 0) {
            currString.append('(');
            helper(ans, currString, openLeft - 1, closedLeft);
            currString.deleteCharAt(currString.length() - 1);
        }
        if (closedLeft > openLeft) {
            currString.append(')');
            helper(ans, currString, openLeft, closedLeft - 1);
            currString.deleteCharAt(currString.length() - 1);
        }
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        if (first == null)
            return head.next;
        ListNode second = head;
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return head;
    }
}

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(ans) != 0) {
                ans = ans.substring(0, ans.length() - 1);
                if (ans.length() == 0)
                    return "";
            }
        }
        return ans;
    }
}

class Solution {
    // D - 3, X - 24. 24 - 3 + 1 = 22个字母.
    // Solution 1
    public int romanToInt(String s) {
        int[] symbolValue = new int[26];
        initialize(symbolValue);
        int ans = symbolValue[s.charAt(0) - 'A'];
        for (int i = 1; i < s.length(); i++) {
            if (symbolValue[s.charAt(i) - 'A'] > symbolValue[s.charAt(i - 1) - 'A']) {
                ans -= 2 * symbolValue[s.charAt(i - 1) - 'A'];
            }
            ans += symbolValue[s.charAt(i) - 'A'];
        }
        return ans;

    }
}

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int max = 0;
        while (left < right) {
            int currentVolume = Math.min(height[left], height[right]) * (right - left);
            max = Math.max(max, currentVolume);
            if (height[left] <= height[right]) {
                left += 1;
            } else {
                right -= 1;
            }
        }
        return max;
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0)
            return false;
        int y = x, num = 0;
        while (y != 0) {
            num = num * 10 + y % 10;
            y /= 10;
        }
        return x == num;
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 1; i < s.length(); i++) {
            int lengthOne = expandAroundCenter(s, i, i);
            int lengthTwo = expandAroundCenter(s, i - 1, i);
            int maxLength = Math.max(lengthOne, lengthTwo);
            if (maxLength > end - start + 1) {
                start = i - maxLength / 2;
                end = i + (maxLength - 1) / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left -= 1;
            right += 1;
        }
        return (right - left - 2) + 1; // 减2意思是退回到上一次满足while条件的状态. 然后获这时候的长度
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ptrOne = l1, ptrTwo = l2, head = new ListNode(0), ptrThree = head;
        int carry = 0;
        while (ptrOne != null || ptrTwo != null || carry != 0) {
            int numOne = ptrOne == null ? 0 : ptrOne.val;
            int numTwo = ptrTwo == null ? 0 : ptrTwo.val;
            int sum = numOne + numTwo + carry;
            int newDigit = sum % 10;
            carry = sum / 10;
            ptrThree.next = new ListNode(newDigit);
            ptrThree = ptrThree.next;
            ptrOne = ptrOne == null ? null : ptrOne.next;
            ptrTwo = ptrTwo == null ? null : ptrTwo.next;
        }
        return head.next;
    }
}

import java.util.*;

class Program {
    static class BST {
        public int value;
        public BST left;
        public BST right;

        public BST(int value) {
            this.value = value;
        }

        public BST insert(int value) {
            BST currentNode = this;
            while (true) {
                if (value < currentNode.value) {
                    if (currentNode.left == null) {
                        BST newNode = new BST(value);
                        currentNode.left = newNode;
                        newNode.left = null;
                        newNode.right = null;
                        break;
                    } else {
                        currentNode = currentNode.left;
                    }
                } else {
                    if (currentNode.right == null) {
                        BST newNode = new BST(value);
                        currentNode.right = newNode;
                        newNode.left = null;
                        newNode.right = null;
                        break;
                    } else {
                        currentNode = currentNode.right;
                    }
                }
            }
            return this;
        }

        public boolean contains(int value) {
            BST currentNode = this;
            while (currentNode != null) {
                if (value == currentNode.value) {
                    return true;
                } else if (value < currentNode.value) {
                    currentNode = currentNode.left;
                } else {
                    currentNode = currentNode.right;
                }
            }
            return false;
        }

        public BST remove(int value) {
            remove(value, null);
            return this;
        }

        public void remove(int value, BST parent) {
            if (value < this.value) {
                if (this.left != null)
                    this.left.remove(value, this);
            } else if (value > this.value) {
                if (this.right != null)
                    this.right.remove(value, this);
            } else {
                if (left != null && right != null) {
                    int minVal = right.getMin();
                    this.value = minVal;
                    right.remove(this.value, this);
                } else if (parent == null) {
                    if (left != null) {
                        this.value = left.value;
                        right = left.right;
                        left = left.left;
                    } else if (right != null) {
                        this.value = right.value;
                        left = right.left;
                        right = right.right;
                    } else {

                    }
                } else if (parent.left == this) {
                    parent.left = this.left != null ? this.left : this.right;
                } else if (parent.right == this) {
                    parent.right = this.left != null ? this.left : this.right;
                }
            }
        }

        public int getMin() {
            if (left == null) {
                return this.value;
            } else {
                return this.left.getMin();
            }
        }
    }
}