双指针法(巧妙思想)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路(来源:labuladong):
可以使用双指针,比较两个升序列表的节点
如图,类似两个拉链,每次拉的时候都会进行节点比较,存入dummy中。
代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧,也就是 dummy
节点,它相当于是个占位符,可以避免处理空指针的情况,降低代码的复杂性。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = l1, p2 = l2;
//双指针法
while (p1 != null && p2 != null){
if (p1.val > p2.val){ //选择较小元素填充到p后
p.next = p2;
p2 = p2.next;
}else {
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
if(p1 != null){
p.next = p1;
}
if(p2 != null){
p.next = p2;
}
return dummy.next;
}
标签:p2,p1,ListNode,思想,巧妙,next,链表,l2,指针
From: https://www.cnblogs.com/chengbb/p/17145056.html