【刷题day06】力扣（LeetCode）每日一刷[21. 合并两个有序链表][206. 反转链表 ][392. 判断子序列]
【刷题day06】力扣（LeetCode）每日一刷[21. 合并两个有序链表][206. 反转链表 ][392. 判断子序列]
CSDN话题挑战赛第2期 参赛话题：学习笔记
刷题打卡，第六天
题目一、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;
}
}贵在坚持：
腾讯云开发者
