LeetCode - 搜索插入位置 / 排序链表
欢迎光临小站：致橡树
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
-
1 <= nums.length <= 104 -
-104 <= nums[i] <= 104 -
nums为 无重复元素 的 升序 排列数组 -
-104 <= target <= 104
解题思路
这段代码实现了合并两个有序链表的功能，采用递归方式实现。
-
创建虚拟头节点：
ListNode head = new ListNode(-1); // 创建一个值为-1的虚拟头节点 -
递归合并过程：
-
基线条件：当两个链表都为空时，递归结束
if (list1 == null && list2 == null) {return head; } -
比较并连接节点：
-
当两个链表都不为空时，比较节点值，取较小者
if (list1.val > list2.val) {head.next = new ListNode(list2.val); // 创建新节点list2 = list2.next; // 移动指针 } else {head.next = new ListNode(list1.val);list1 = list1.next; } -
当一个链表为空时，直接连接另一个链表的节点
else if (list1 == null) {head.next = new ListNode(list2.val);list2 = list2.next; } else if (list2 == null) {head.next = new ListNode(list1.val);list1 = list1.next; }
-
-
-
递归调用：
return doMergeTwoLists(head.next, list1, list2); // 处理下一个节点 -
返回结果：
return head.next; // 跳过虚拟头节点，返回真正的头节点
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head = new ListNode(-1);doMergeTwoLists( head, list1, list2);return head.next;}public ListNode doMergeTwoLists(ListNode head, ListNode list1, ListNode list2) {if (list1 == null && list2 == null) {return head;}if (list1 != null && list2 != null) {if (list1.val > list2.val) {head.next = new ListNode(list2.val);list2 = list2.next;} else {head.next = new ListNode(list1.val);list1 = list1.next;}}else if (list1 == null) {head.next = new ListNode(list2.val);list2 = list2.next;}else if (list2 == null) {head.next = new ListNode(list1.val);list1 = list1.next;}return doMergeTwoLists( head.next, list1, list2);}
}排序链表
给你链表的头结点 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
解题思路
整体算法流程
-
分割（Split）：递归地将链表分成两半
-
排序（Sort）：对每一半递归地进行排序
-
合并（Merge）：将两个已排序的子链表合并成一个有序链表
方法分解说明
sortList(ListNode head)
public ListNode sortList(ListNode head) {return doSortList(head, null); // 初始调用，tail设为null表示链表末尾
}-
入口方法：启动排序过程
-
参数：只需要传入链表头节点
-
返回值：排序后的链表头节点
doSortList(ListNode head, ListNode tail)
public ListNode doSortList(ListNode head, ListNode tail) {// 基线条件：当子链表只有一个节点时返回if (head.next == tail) {head.next = null; // 断开连接，形成独立节点return head;}// 快慢指针找中点ListNode slow = head;ListNode fast = head;while (fast != tail && fast.next != tail) {slow = slow.next;fast = fast.next.next;}ListNode mid = slow;// 递归排序左右两部分ListNode left = doSortList(head, mid);ListNode right = doSortList(mid, tail);// 合并已排序的两部分return doMerge(left, right);
}-
分割策略：
-
使用快慢指针找到链表中点
-
快指针每次走两步，慢指针每次走一步
-
当快指针到达尾部时，慢指针正好在中点
-
-
递归处理：
-
对左半部分(head到mid)递归排序
-
对右半部分(mid到tail)递归排序
-
doMerge(ListNode left, ListNode right)
public ListNode doMerge(ListNode left, ListNode right) {ListNode dummy = new ListNode(-1); // 虚拟头节点ListNode temp = dummy;// 比较两个链表的节点值，选择较小的接入结果链表while (left != null && right != null) {if (left.val > right.val) {temp.next = right;right = right.next;} else {temp.next = left;left = left.next;}temp = temp.next;}// 处理剩余节点while (left != null) {temp.next = left;temp = temp.next;left = left.next;}while (right != null) {temp.next = right;temp = temp.next;right = right.next;}return dummy.next; // 返回合并后的链表头
}-
合并策略：
-
创建虚拟头节点简化操作
-
比较两个链表的当前节点值
-
将较小值的节点连接到结果链表
-
移动相应链表的指针
-
-
剩余处理：
-
当其中一个链表遍历完后
-
直接将另一个链表的剩余部分连接到结果链表
-
关键点解析
快慢指针找中点
while (fast != tail && fast.next != tail) {slow = slow.next;fast = fast.next.next;
}-
终止条件：
-
fast == tail：处理奇数长度链表 -
fast.next == tail：处理偶数长度链表
-
-
结果：
-
slow指针最终指向中点
-
递归终止条件
if (head.next == tail) {head.next = null; // 重要：断开原有连接return head;
}-
当子链表只有一个节点时终止递归
-
必须断开
next指针，否则会影响合并过程
虚拟头节点技巧
ListNode dummy = new ListNode(-1);
ListNode temp = dummy;
// ...
return dummy.next;-
简化链表操作
-
避免处理头节点的特殊情况
完整代码
class Solution {public ListNode sortList(ListNode head) {return doSortList(head, null);}public ListNode doSortList(ListNode head, ListNode tail) {if (head.next == tail) {head.next = null;return head;}ListNode slow = head;ListNode fast = head;while (fast != tail && fast.next != tail) {slow = slow.next;fast = fast.next.next;}ListNode mid = slow;ListNode left = doSortList(head, mid);ListNode right = doSortList(mid, tail);return doMerge(left, right);}public ListNode doMerge(ListNode left, ListNode right) {ListNode dummy = new ListNode(-1);ListNode temp = dummy;while (left != null && right != null) {if (left.val > right.val) {temp.next = right;right = right.next;} else {temp.next = left;left = left.next;}temp = temp.next;}while (left != null) {temp.next = left;temp = temp.next;left = left.next;}while (right != null) {temp.next = right;temp = temp.next;right = right.next;}return dummy.next;}
}