算法练习——合并两个有序链表

2021年1月18日LeetCode每日一题为721. 账户合并,想到用并查集,用邮箱作键,但是却不知道怎么样去实现,于是便选择完成21. 合并两个有序链表,这道题挺简单的,熟悉链表特性就容易完成,先过滤两个链表都为空和各自为空的情况,然后用一个临时变量来指代第一个元素值较小的链表为主链表,一个临时变量保存另一个链表,一个变量指向上一个节点,循环遍历元素较小的链表,直到元素值大于另一个链表的当前节点元素值时,将这个节点接入到主链表中,直到链表合并完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for singly-linked list.
* 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) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = l1, pre = l1, temp = l2;
if (l2.val < l1.val) {
head = l2;
temp = l1;
}
ListNode ret = head;
while (temp != null) {
while (head != null && temp.val >= head.val) {
pre = head;
head = head.next;
}
ListNode t = temp.next;
temp.next = head;
pre.next = temp;
pre = temp;
temp = t;
}
return ret;
}
}

这次的练习熟悉链表很容易就能写出来,然后就需要考虑两个链表的边界问题。最近做题的时间基本上都推到晚上了,果然回到家之后琐碎的事情就特别多,总之还是要坚持完成每天的算法练习,保持算法的思维,经过一定的周期一定可以看到自己的成长。