分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2： 输入：head = [2,1], x = 2 输出：[1,2]
提示： 链表中节点的数目在范围 [0, 200] 内 -100 <= Node.val <= 100 -200 <= x <= 200
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummyHead1 = new ListNode(0);
ListNode dummyHead2 = new ListNode(0);
ListNode node1 = dummyHead1;
ListNode node2 = dummyHead2;
while (head != null) {
if (head.val < x) {
node1.next = head;
head = head.next;
node1 = node1.next;
node1.next = null;
} else {
node2.next = head;
head = head.next;
node2 = node2.next;
node2.next = null;
}
}
node1.next = dummyHead2.next;
return dummyHead1.next;
}
}
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
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 l1, ListNode l2) {
ListNode h = new ListNode(0, null);
ListNode p = h;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
p = l1;
l1 = l1.next;
} else {
p.next = l2;
p = l2;
l2 = l2.next;
}
}
if (l1 != null) {
p.next = l1;
} else {
p.next = l2;
}
return h.next;
}
}
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 进阶：
- 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = floor(nums, target);
result[1] = ceil(nums, target);
return result;
}
private int floor(int[] nums, int target) {
int left = -1;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (target <= nums[mid]) {
right = mid - 1;
} else {
left = mid;
}
}
if (left + 1 < nums.length && nums[left + 1] == target) {
return left + 1;
} else {
return -1;
}
}
private int ceil(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (target >= nums[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
if (right - 1 >= 0 && nums[right - 1] == target) {
return right - 1;
} else {
return -1;
}
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????