class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        if(s1.equals(s2)) return true;          //两个字符串相等，true
       List<Integer> diff = new ArrayList<>(); //使用集合记录不相等字符的位置（下标）
        for(int i = 0;i < s1.length();++i){     //遍历两个字符串
            if(s1.charAt(i) != s2.charAt(i))    //相同位置下字符不相等
            diff.add(i);                        //记录下来
            if(diff.size() > 2) return false;   //记录下的下标数大于2，false
        }
        if(diff.size() == 1) return false;      //只有一个位置不等，也不符合，false
        int a = diff.get(0),b = diff.get(1);    //取出记录的下标
        //判断交换位置后是否与s1相等
        return s1.charAt(a) == s2.charAt(b) && s2.charAt(a) == s1.charAt(b);
    }
}

/**
 * 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 oddEvenList(ListNode head) {
        if(head == null) return null;             //链表为空，直接返回空值
        ListNode odd = head;                      //创建奇数链表，头节点为原始链表的第一个节点
        ListNode even = head.next;                //创建偶数链表，头节点为原始链表的第二个节点
        ListNode temp = even;                     //额外创建链表指向偶数链表头节点，方便后续拼接
        while(temp != null && temp.next != null){ 
            odd.next = temp.next;   //奇数链表节点指向其后偶数节点的下一位置
            odd = odd.next;         //后移一位
            temp.next = odd.next;   //偶数数链表节点指向其后奇数节点的下一位置
            temp = temp.next;       //后移一位
        }
        odd.next = even;            //技术链表尾巴节点指向偶数链表头节点
        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 sortList(ListNode head) {
       return sort(head,null);               //调用递归方法
    }
    //递归方法
    public ListNode sort(ListNode head,ListNode tail){
        if(head == null){      //头节点为空，返回空值
            return head;
        }
        if(head.next == tail){ //节点最终平分至单节点
            head.next = null;  //结点指向空值
            return head;       //返回节点
        }
        ListNode fast = head,slow = head;  //设置快慢指针
        while(fast != tail){               //快指针遍历到结尾前
            slow = slow.next;              //满指针后移
            fast = fast.next;              //快指针后移
            if(fast != tail){              //依旧未到尾部
            fast = fast.next;              //快指针第二次后移
            }
        }
        ListNode mid = slow;               //中间节点就是满指针当前节点
        ListNode list1 = sort(head,mid);   //同样方式平分左子链表
        ListNode list2 = sort(mid,tail);   //同样方式平分右子链表
        ListNode sorted = merge(list1,list2);  //调用归并操作方法
        return sorted;                         //返回升序链表头节点
    }
    public static ListNode merge(ListNode list1,ListNode list2){
        //创建新的链表，存放升序节点
        ListNode list = new ListNode();
        ListNode temp1 = list1;    //两个相邻的链表
        ListNode temp2 = list2;
    ListNode temp = list;
    while(temp1 != null && temp2 != null){ //对相邻链表进行归并操作
        if(temp1.val <= temp2.val){        //较小的节点放入链表
            temp.next = temp1;
            temp1 = temp1.next; 
        }else{
            temp.next = temp2;             //较小的节点放入链表
            temp2 = temp2.next;            
        }
        temp = temp.next;
    }
    if(temp1 != null){          //一个链表遍历完，相邻链表剩下的一个节点存入新链表
        temp.next = temp1;
    }
    if(temp2 != null){
        temp.next = temp2;
    }
    return list.next;           //返回升序链表
    }
}