目录
LeetCode之路——21. 合并两个有序链表
分析：
LeetCode之路——19. 删除链表的倒数第 N 个结点
分析：
LeetCode之路——21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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均按 非递减顺序 排列
分析：
1.可以直接根据题意定义一个新的链表节点res，建议使用哨兵节点方便头节点操作。
2.l1和l2取当前节点比较，小的追加到res，直至l1为空或l2为空，非空的部分直接追加到res。
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 哨兵节点ListNode prehead = new ListNode(-10);
ListNode res = prehead;while (list1 != null && list2 != null) {if (list1.val < list2.val) {res.next = list1;list1 = list1.next;} else {res.next = list2;list2 = list2.next;}res= res.next;}
// l1和l2剩余节点可以直接追加在res后面res.next = list1 == null? list2:list1;return prehead.next;}
}
-
时间复杂度：O(n+m)
-
空间复杂的：O(1)
LeetCode之路——19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 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
分析：
解法一：常规思路
-
从头遍历链表，获取链表长度m。
-
倒数第n个节点就是m-n+1个节点。
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {int m = getLength(head);// 哨兵节点方便头节点为空时，获取sentinel.next。ListNode sentinel = new ListNode(0, head);ListNode curr = sentinel;for (int i = 1; i < m - n + 1; i++) {curr = curr.next;}curr.next = curr.next.next;ListNode res = sentinel.next;return res;}
// 获取链表长度public int getLength(ListNode head) {int m = 0;while (head != null) {m++;head = head.next;}return m;}
}
解法二：双指针
-
快慢指针同时遍历，快指针需要比慢指针超前n个节点的距离。
-
当快指针走到末尾节点，慢指针当前节点就是要被删除的节点
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode sentinel = new ListNode(0, head);ListNode fast = head;ListNode slow = sentinel;
for (int i = 0; i < n; i++) {fast = fast.next;}
while (fast != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;ListNode res = sentinel.next;return res;}
}
