Logo

菜单

wayne
wayne
发布于 2025-08-05 / 2 阅读
0
0

LeetCode - 搜索插入位置 / 排序链表

#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

解题思路

这段代码实现了合并两个有序链表的功能，采用递归方式实现。

  1. 创建虚拟头节点：

    ListNode head = new ListNode(-1);  // 创建一个值为-1的虚拟头节点

  2. 递归合并过程：

    • 基线条件：当两个链表都为空时，递归结束

      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;
}

  3. 递归调用：

    return doMergeTwoLists(head.next, list1, list2);  // 处理下一个节点

  4. 返回结果：

    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

 

解题思路

整体算法流程

  1. 分割（Split）：递归地将链表分成两半

  2. 排序（Sort）：对每一半递归地进行排序

  3. 合并（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;
	}
}

LeetCode - 合并两个有序...

评论