class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode res = new ListNode();
        ListNode move = res;
        while(list1 != null || list2 != null){
            if(list1 == null){
                move.next = list2;
                break;
            }
            else if(list2 == null){
                move.next = list1;
                break;
            }
            else if(list1.val <= list2.val){
                move.next = list1;
                list1 = list1.next;
                move = move.next;
            }else{
                move.next = list2;
                list2 = list2.next;
                move = move.next;
            }
        }
        return res.next;
    }
}

/**
 * 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 swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode temp = head.next;
        if(head.next.next != null){
            head.next = head.next.next;
        }else{
            head.next.next = head;
            head = head.next;
            head.next.next = null;
            return head;
        }
        temp.next = head;
        head = temp;
        ListNode i  = head.next;
        while(i.next != null && i.next.next != null){
            ListNode t3 = i.next;
            ListNode t4 = i.next.next;
            ListNode t5 = null;
            if(t4.next != null){
                t5 = t4.next;
            }
            i.next = t4;
            t4.next = t3;
            if(t5 == null){
                t3.next = null;
                return head;
            }
            t3.next = t5;
            i = i.next.next;
        }
        return head;
    }
}

/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode p = head;
        ListNode s = head;
        int i;
        int[] temp = new int[k];
        while(s.next != null){
            int count = 0;
            for(i = 0;i < k ;i++){
                temp[i] = s.val;
                if(s.next != null){
                    s = s.next;
                    count++;
                }
                
            }
            if(i == k && (count == k - 1 || count == k)){
                for(i = 0;i < k;i++){
                p.val = temp[k - i - 1];
                p = p.next;
            }
            }
        }
        return head;
    }
}

class Solution {
    public double myPow(double x, int n) {
        if(x > -0.5 && x < 0.5 && n > 50){
            return 0;
        }
        if(x == 1){
            return 1;
        }
        if(x == -1){
            return n % 2 == 0 ? 1 : -1;
        }
        if(n == 0){
            return 1;
        }
        if(n == 1){
            return x;
        }
        if(n == -1){
            return 1.0/x;
        }
        int a = n / 2;
        int b = n - a;
        return myPow(x,a) * myPow(x,b);
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode res = new ListNode();
        res.next = head;
        ListNode node = res;
        while (node.next != null){
            if(node.next.val == val){
                if (node.next.next != null) node.next = node.next.next;
                else node.next = null;
            }else {
                node = node.next;
            }

        }
        return res.next;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = null;
        ListNode n = head;
        while(n != null){
            ListNode temp = n;
            n = n.next;
            temp.next = p;
            p = temp;
        }
        return p;
    }
}