-
合并两个有序链表
image.png
思路：先创建一个头结点，然后同时遍历两个链表，将val小的不断插入到新的链表中。最后将没有遍历完的那个的链表直接链接到新链表的结尾即可。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode first = new ListNode();
ListNode index = new ListNode();
index = first;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
index.next = l1;
index = index.next;
l1 = l1.next;
} else {
index.next = l2;
index = index.next;
l2 = l2.next;
}
}
if (l1 == null) {
index.next = l2;
}
if (l2 == null) {
index.next = l1;
}
return first.next;
}
}
-
删除有序数组中的重复项（*）
image.png
思路：
需要借助双指针：一个指针slow表示不同的元素将要填充到的位置，另一个指针fast用于遍历获取不同元素的下标。
fast和slow均从1开始。利用fast对数组遍历，当fast所指元素与前一个元素不同时，表明可以将fast所指元素插入到slow处；当fast所指元素与前一个相同时，fast就++
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 1;
int fast = 1;
while (fast < nums.length) {
if (nums[fast] != nums[fast - 1]) {//找到了不同的元素
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
-
移除元素
image.png
思路：循环，并用一个count记录目前等于val的数组元素的个数，每个元素都向前移动count个位置即可
class Solution {
public int removeElement(int[] nums, int val) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == val) {
count++;
} else {
nums[i - count] = nums[i];
}
}
return nums.length - count;
}
}
