刷题打卡，第 二十八 天
题目一、1790. 仅执行一次字符串交换能否使两个字符串相等
题目二、328. 奇偶链表
题目三、148. 排序链表
题目一、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; //两个字符串相等，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); } }
提交结果：
题目二、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; //返回升序链表 } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
