剑指Offer:合并两个排序的链表【25】

剑指Offer:合并两个排序的链表【25】

题目描述

  输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

题目分析

  双指针问题的经典案例,合并有序链表。

剑指Offer:合并两个排序的链表【25】

  上下两个指针,谁小谁先走,先走的是较小的蓝1,结果集新增蓝1.

剑指Offer:合并两个排序的链表【25】

  上下两个指针,谁小谁先走,先走的是较小的紫2,结果集新增紫2.

剑指Offer:合并两个排序的链表【25】

  按照这个逻辑接着往后走即可!这个逻辑还是相对比较清晰的。

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;
}

  

  

上一篇:剑指offer——25合并两个排序的链表


下一篇:《剑指offer》合并两个排序的链表