剑指Offer:合并两个排序的链表【25】
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
题目分析
双指针问题的经典案例,合并有序链表。
上下两个指针,谁小谁先走,先走的是较小的蓝1,结果集新增蓝1.
上下两个指针,谁小谁先走,先走的是较小的紫2,结果集新增紫2.
按照这个逻辑接着往后走即可!这个逻辑还是相对比较清晰的。
Java题解
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head1 = list1;
ListNode head2 = list2;
ListNode newHead = new ListNode(-1);
ListNode ptr = newHead;
while (head1!=null&&head2!=null){
if(head1.val<=head2.val){
ptr.next = head1;
head1 = head1.next;
}else{
ptr.next = head2;
head2 = head2.next;
}
ptr = ptr.next;
}
if(head1==null)
ptr.next = head2;
else
ptr.next = head1;
return newHead.next;
}