题目一、1790. 仅执行一次字符串交换能否使两个字符串相等

原题链接：1790. 仅执行一次字符串交换能否使两个字符串相等

题目描述：

给你长度相等的两个字符串 s1 和 s2 。一次字符串交换操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
如果对其中一个字符串执行最多一次字符串交换就可以使两个字符串相等，返回 true ；否则，返回 false 。
/
示例 1：
输入：s1 = “bank”, s2 = “kanb”
输出：true
解释：例如，交换 s2 中的第一个和最后一个字符可以得到 “bank”
/
示例 2：
输入：s1 = “attack”, s2 = “defend”
输出：false
解释：一次字符串交换无法使两个字符串相等
/
示例 3：
输入：s1 = “kelb”, s2 = “kelb”
输出：true
解释：两个字符串已经相等，所以不需要进行字符串交换
/
示例 4：
输入：s1 = “abcd”, s2 = “dcba”
输出：false
/
提示：

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 和 s2 仅由小写英文字母组成

解题思路：
题目已经给定我们两个长度相同字符串s1和s2，要求我们判断字符串s2可否仅通过一次交换得到s1。

在最开始，我们应该先判断两个字符串s1和s2是否相等，相等就直接返回true即可。

通过思考，我们可以知道，交换一次，就会变动两个位置的字符，同时代表着字符串s2有两个位置的字符是与字符串s1不相同的，这么一来我们就找到了突破点。

我们同时遍历两个字符串，比较两字符串在相同位置的字符是否相等，如果不相等就将下标记录下来。

当我们记录下来的下标数量大于2时，就知道无法仅执行一次字符串交换使两个字符串相等，直接返回false。

当遍历完成了，我们会得到两种情况：

①被记录下的下标只有一个，这也是无法通过最多一次交换相等的，false；

②被记录的下标有两个，这时候，我们需要判断字符串s2中，交换这两个位置的字符可以使得s2与s1相等。相等则返回true，否则返回false；

提交代码：

class Solution {public boolean areAlmostEqual(String s1, String s2) {if(s1.equals(s2)) return true;          //两个字符串相等，trueList<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;      //只有一个位置不等，也不符合，falseint a = diff.get(0),b = diff.get(1);    //取出记录的下标//判断交换位置后是否与s1相等return s1.charAt(a) == s2.charAt(b) && s2.charAt(a) == s1.charAt(b);}
}

提交结果：

题目二、328. 奇偶链表

原题链接：328. 奇偶链表

题目描述：

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
/
示例 1:

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
/
示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
/
提示:

n == 链表中的节点数
0 <= n <= 104
-106 <= Node.val <= 106

解题思路：
第一个节点是奇数，第二个节点是偶数，往后的节点也是 奇数-偶数-奇数--的位置顺序。

题目要求我们将所有奇数节点连在一块，所有偶数节点连在一块，且奇数连链表于偶数链表拼接。

必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

我们可以创建两个新的链表，分别代表奇数链表与偶数链表，第一个节点是奇数，作为奇数链表的头节点；第二个节点为偶数，作为偶数链表的头节点。

因为奇数偶数是交替的，也就是奇数下一个节点为偶数，偶数下一个节点为奇数。我们就可以将所有奇数节点指向其后偶数节点的下一节点，偶数节点也指向其后奇数节点的下一个节点。

当我们遍历完原始链表，也就完成了奇数链表与偶数链表的节点连接，这时候将奇数链表末尾节点指向偶数链表头节点即可。

提交代码：

/*** 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;                //返回头节点，也是奇数链表的头节点}
}

提交结果：

题目三、148. 排序链表

原题链接：148. 排序链表

题目描述：

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。
/
示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]
/
示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
/
示例 3：
输入：head = []
输出：[]
/
提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

解题思路：
我们需要给链表节点值进行排序。

我是用的排序方法是归并排序，我们知道，归并排序首先需要获得排序元素的中间元素位置。

但是链表又没有办法向数组那样通过下标获取，所以我们需要使用到快慢指针，快指针一次走两个节点，慢指针一次走一个节点，那么快指针遍历到链表结尾时，我们的慢指针所在位置就是中间节点的位置。

这时候我们借助递归，用同样的方式将每一个子链表通过中间节点平分，最后得到单个的节点，然后相邻的两个节点按照升序合并，这就是归并操作。

我们不断对相邻的两个节点进行归并操作，将归并好的节点按照顺序放入准备好的新链表中，最后返回新链表的头节点即可！

最主要还是理解归并排序的步骤、模板。

提交代码：

/*** 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;           //返回升序链表}
}