题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
样例
输入:1->3->5 , 2->4->5
输出:1->2->3->4->5->5
时间复杂度
时间复杂度O(N),空间复杂度O(1)
Java 代码
创建两个头结点指向两个链表,像操作删除链表头结点一样,把较小的头结点不断的抛出
再用一个新的链表的next不断连接被抛出的点即可
class Solution {
public ListNode merge(ListNode l1, ListNode l2) {
ListNode lm = new ListNode(0);
ListNode p1 = new ListNode(1);
ListNode p2 = new ListNode(2);
ListNode m = lm;
p1.next = l1;
p2.next = l2;
while(p1.next != null && p2.next != null){
if(p1.next.val < p2.next.val){
m.next = p1.next;
p1.next = p1.next.next;
}else{
m.next = p2.next;
p2.next = p2.next.next;
}
m = m.next;
}
if(p1.next != null) m.next = p1.next;
if(p2.next != null) m.next = p2.next;
return lm.next;
}
}