力扣82删除链表中的重复元素
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
示例 1:
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
示例 2:
输入:head = [1,1,1,2,3]
输出:[2,3]
题目分析
删除链表中的重复元素
解题思路
其实有关链表的题都可以先将链表存到数组中,进行想要的改变后再存回链表,但是这样就失去了练习链表的意义
因为删除重复元素实现覆盖需要被覆盖的上一个结点和下一个结点,所以我们需要判断cur->next,cur->next->next是否为空进入while循环,以及是否相等进入if语句
注意:因为有可能要删除头节点,所以要设置虚拟头节点
代码实现
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* dummy = new ListNode(0, head);ListNode* cur = dummy;while (cur->next && cur->next->next) {if (cur->next->val == cur->next->next->val) {int x = cur->next->val;while (cur->next && cur->next->val == x) {cur->next = cur->next->next;}}else {cur = cur->next;}}return dummy->next;}
};
力扣23合并k个有序链表
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
题目分析
与合并2个有序链表类似
解题思路
先合并前两个链表,再不断将新链表与下一个链表合并
代码实现
class Solution {
public:ListNode* mergeTwoLists(ListNode *a, ListNode *b) {if ((!a) || (!b)) return a ? a : b;ListNode head, *tail = &head, *aPtr = a, *bPtr = b;while (aPtr && bPtr) {if (aPtr->val < bPtr->val) {tail->next = aPtr; aPtr = aPtr->next;} else {tail->next = bPtr; bPtr = bPtr->next;}tail = tail->next;}tail->next = (aPtr ? aPtr : bPtr);return head.next;}ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode *ans = nullptr;for (int i = 0; i < lists.size(); ++i) {ans = mergeTwoLists(ans, lists[i]);}return ans;}
};