1.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例一:
示例二:
示例三:
1.双指针求解
由于前面已经介绍过采用双指针合并两个有序数组,这里同样可以采用双指针的思路合并两个有序链表。
合并方法如下:如果list1.val<list2.val,则将当前结果集p指向list1,同时list1链表与结果集链表指针同时向后移动;否则,则将list2链表与结果集链表指针同时向后移动。一旦某一个链表指向为空后,则可以直接将当前的结果集链表指向另一个非空链表,最后返回即可。具体代码如下所示:
/**
* 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 list1, ListNode list2) {
if(list1 ==null) return list2;
if(list2 ==null) return list1;
ListNode result=new ListNode(0);
ListNode p=result;
while(list1!=null && list2!=null){
if(list1.val<list2.val){
p.next=list1;
list1=list1.next;
}else{
p.next=list2;
list2=list2.next;
}
p=p.next;
}
if(list1!=null)
p.next=list1;
if(list2!=null)
p.next=list2;
return result.next;
}
}
2.GIF动图演示
如果对代码不能够清晰的理解与认识,可以借助GIF动图演示过程来深刻理解双指针代码实现。
3.时间复杂度分析
分析代码的执行过程可知,双指针分别对链表进行逐一遍历,因此最差的时间复杂度为 O ( m + n ) , m O(m+n),m O(m+n),m为链表1的长度, n n n为链表2的长度。
因为每次循环迭代中, l i s t 1 list1 list1 和 l i s t 2 list2 list2 只有一个元素会被放进合并链表中, 因此 w h i l e while while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O ( n + m ) O(n+m) O(n+m)。
4.递归实现
这里根据分析可以得知,子问题与原问题的求解过程完全一致,符合递归的使用条件
如果 l i s t 1 list1 list1 或者 l i s t 2 list2 list2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l i s t 1 list1 list1 和 l i s t 2 list2 list2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。具体代码如下所示:
/**
* 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 list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
} else if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
5.递归GIF动图演示
下图是递归算法合并有序链表的GIF动图演示,读者可以借助图形来理解代码。
6.时间复杂度分析
时间复杂度: O ( n + m ) O(n + m) O(n+m),其中 n n n 和 m m m 分别为两个链表的长度。因为每次调用递归都会去掉 l i s t 1 list1 list1 或者 l i s t 2 list2 list2 的头节点(直到至少有一个链表为空),函数 m e r g e T w o L i s t mergeTwoList mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O ( n + m ) O(n+m) O(n+m).时间复杂度与迭代双指针类似,但是代码实现更加简洁明了。具体代码在LeetCode中的执行结果如下所示:
2.删除排序链表中的重复元素
给定一个已排序的链表的头 h e a d head head,删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例一:
示例二:
1.一次遍历
由于给定的链表是排好序的,因此重复的元素在链表中出现的位置是连续的,因此我们只需要对链表进行一次遍历,就可以删除重复的元素。
具体地,我们从指针 cur \textit{cur} cur指向链表的头节点,随后开始对链表进行遍历。如果当前 cur \textit{cur} cur 与 cur.next \textit{cur.next} cur.next对应的元素相同,那么我们就将 cur.next \textit{cur.next} cur.next从链表中移除;否则说明链表中已经不存在其它与 cur c u r \textit{cur}cur curcur 对应的元素相同的节点,因此可以将 cur \textit{cur} cur 指向 cur.next \textit{cur.next} cur.next。
当遍历完整个链表之后,我们返回链表的头节点即可。
/**
* 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 deleteDuplicates(ListNode head) {
if(head==null)
return head;
ListNode cur=head;
while(cur.next!=null){
if(cur.next.val==cur.val){
cur.next=cur.next.next;
}else{
cur=cur.next;
}
}
return head;
}
}
2.时间复杂度分析
由于是对链表的一次遍历,所以时间复杂度毫无疑问就是 O ( n ) O(n) O(n),具体代码在LeetCode中的执行情况如下所示:
3.递归实现
每当我们处理完链表中的一个节点,那么这个链表就便短了,而这个变短的链表与原链表在处理方式上完全一致,所以这时候可以利用递归来做!
/**
* 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 deleteDuplicates(ListNode head) {
if(head==null || head.next==null) return head;
head.next=deleteDuplicates(head.next);
return head.val==head.next.val?head.next:head;
}
}
4.时间复杂度分析
采用递归代码会更加简洁,但是会更难理解。递归的方式时间复杂度与上面的迭代算法是一样的,都是 O ( n ) O(n) O(n)。具体代码在LeetCode的执行情况如下所示: