刷题打卡，第六天
题目一、21. 合并两个有序链表
题目二、206. 反转链表
题目三、392. 判断子序列
题目一、21. 合并两个有序链表
原题链接：21. 合并两个有序链表
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：
题目很简单。
既然给出的链表已经排好序，我们只需要对比当前节点的元素大小，较小的元素节点优先放入新链表中，重复操作，最后返回新链表即可：
/** * 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) { ListNode list3 = new ListNode();//头节点 ListNode l3 = list3; while(list1 != null && list2 != null){//两个有序链表都不为空 if(list1.val <= list2.val){ //比较两链表节点值 l3.next = list1; //值较小的节点传入新链表 list1 = list1.next; //指向下一节点 }else{ l3.next = list2; list2 = list2.next; } l3 = l3.next; //指针向后移动，准备接收新值 } l3.next = list1 == null?list2:list1; //将剩下的一个节点也放入新链表 //也可以在其中一个链表为空时，直接返回另一个链表 return list3.next; } }
提交结果：
题目二、206. 反转链表
原题链接：206. 反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
/
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
/
> 输入：head = [1,2]
输出：[2,1]
/
示例 3：
输入：head = []
输出：[]
解题思路：
循环地让每一个节点都指向其前一个结点即可，
也就是让当前节点的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 reverseList(ListNode head) { ListNode list = null;//用list来记录反转后链表的头节点 ListNode curr = head;//curr表示当前位置 while(curr != null){//当不为空时 ListNode next = curr.next;//新建next，用于存放下一节点位置 curr.next = list; //当前节点指向前一个结点 list = curr; //当前节点作为表头，成功完成一次反转 curr = next; //以next作为当前位置（指针后移），重复上述操作 } return list; //成功反转后，返回表头 } }
提交结果：
题目三、392. 判断子序列
原题链接：392. 判断子序列
题目描述：
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true
示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false
解题思路：
设定两个指针，分表指向两串字符串 s 和 t 的初始位置，相同就同时向后移动，且记录下移动次数，若不相同，只移动 t 串指针。
最终若第一个指针完全扫过 s 串，就说明 s 为字串。
代码：
class Solution { public boolean isSubsequence(String s, String t) { int n = s.length(), m = t.length(); int i = 0, j = 0; while (i < n && j < m) { if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == n; } }
提交结果：
下面这个是最开始写的版本…有点蠢：给大家乐呵乐呵
class Solution { public boolean isSubsequence(String s, String t) { if(s.length()==0 || s.equals(t)) return true; char x,y; for(int i=0,j=0; i < t.length();i++){ x = s.charAt(j);y=t.charAt(i); if(x == y){ j++;i++; if(j >= s.length()){ return true;} if(i >= t.length()){return false;} x = s.charAt(j);y=t.charAt(i); }else{ i++; if(i >= t.length()){return false;} y=t.charAt(i); } i--; } return false; } }
贵在坚持：
