LeetCode 第19~21题

LeetCode 第19题：删除链表的倒数第N个结点

题目描述

给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

难度：中等
题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

示例1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

 示例2：

输入：head = [1], n = 1
输出：[]

示例3：
 

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为sz
• 1<=sz<=30
• 0<=Node.val<=100
• 1<=n<=sz

 解题思路：
方法一：双指针（一次扫描）

• 创建虚拟头节点，简化边界情况；
• 快指针先走n步
• 快慢指针同时移动，直到快指针到达末尾
• 删除慢指针的下一个节点
• 返回虚拟头节点的下一个节点
• 时间复杂度：O（1），其中n是链表长度；
• 空间复杂度：O（1）

public class Solution{public ListNode RemoveNthFromEnd(ListNode head,int n){//创建虚拟头节点ListNode dummy = new ListNode(0,head);ListNode fast = dummy;ListNode slow = dummy;//快指针先走n步for(int i=0;i<n;i++)fast = fast.next;//快慢指针一起移动while(fast.next!=null){fast = fast.next;slow = slow.next;}//删除目标节点slow.next = slow.next.next;return dummy.next;}
}

方法二：计算长度（两趟扫描）

先遍历一遍计算链表长度，再遍历一遍删除指定节点。

public class Solution{public ListNode RemoveNthFromEnd(ListNode head,int n){//创建虚拟头节点ListNode dummy = new ListNode(0,head);//计算链表长度int length= 0;ListNode current head;while(current!=null){length++,current=current.next;}//找到要删除节点的前一个节点current=dummy;for(int i=0;i<length-n;i++)  current = current.next;current.next = current.next.next;return dummy.next;}
}

LeetCode 第20题：有效的括号

题目描述

给定一个只包括'(',')','[',']','{','}'的字符串s，判断字符串是否有效。有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合
• 每个右括号都有一个对应的相同类型的左括号

难度：简单

题目链接：20. 有效的括号 - 力扣（LeetCode）

示例1：
 

输入：s = "()"
输出：true

示例2：
 

输入：s = "()[]{}"
输出：true

示例3：
 

输入：s = "(]"
输出：false

提示：

• 1<=s.length<=10^4
• s仅由括号‘()[]{}’组成

解题思路：栈

• 创建一个栈来存储左括号
• 遍历字符串

1. 如果是左括号，入栈；
2. 如果是右括号：判断栈的情况，如果为空返回false。如果与栈顶括号不匹配返回false;如果匹配弹出栈顶元素。

• 最后检查栈是否为空
• 时间复杂度：O（n），其中n是字符串长度
• 空间复杂度：O（n），最坏情况下需要存储所有字符

public class Solution
{public bool IsValid(string s){if(s.Length%2==1)  return false;//奇数不匹配//创建栈来存储左括号Stack<char> stack = new Stack<char>();//遍历字符串foreach(char c in s){//如果是左括号，入栈if(c=='('||c=='['||c=='{') stack.push(c);else{//如果栈为空，falseif(stack.Count==0)   return false;//获取栈顶元素char top = stack.pop();if(c==')'&& top!='(' || c==']'&& top!='[' || c=='}'&&top!='{') return false;}}return stack.Count==0;}}

LeetCode 第21题：合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。

难度：简单
题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

 示例2：
 

输入：l1 = [], l2 = []
输出：[]

示例3：
 

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是[0,50]
• -100<=Node.val<=100
• L1和L2均按非递减顺序排列

解题思路：
方法一：迭代法
使用迭代的方法，逐个比较两个链表的节点值，将较小的节点添加到结果链表中

• 创建虚拟头节点（dummy node）
• 使用指针遍历两个链表

1. 比较当前节点的值
2. 将较小的节点接入结果链表
3. 移动对应链表的指针

• 处理剩余节点
• 返回虚拟头节点的下一个节点
• 时间复杂度：O（n+m）,其中n和m是两个链表的长度
• 空间复杂度：O(1)

public class Solution{public ListNode MergeTwoLists(ListNode list1,ListNode list2){//创建虚拟头节点ListNode dummy = new ListNode(0);ListNode current dummy;//同时遍历两个链表while(list1!=null && list2!=null){if(list1.val<=list2.val) current.next=list1,list1=list1.next;else current.next= list2,list2=list2.next;current=current.next;}//处理剩余节点current.next = list1 ?? list2;//谁还有剩余，便直接添加进去return dummy.next;}}

方法二：递归法--利用递归的特性，将问题分解为更小的子问题

• 比较两个链表当前节点的值
• 选择较小的节点作为当前节点
• 递归处理剩余部分
• 基线条件是其中一个链表为空