转载

【Google-onsite面经】Merge Two Sorted List

题目来源

时间是2016年7月21日，MTV onsite，第三轮，第一题。

题目内容

参考leetcode的第21题，要求很简单，将两个排好序的链表合并成一个新的排好序链表。 1->2->5 和 3->4->6 两个输入值，得到 1->2->3->4->5->6 。这题简单的就像小时候动画片结束之后的有奖问答。

做法

两个链表各起一个指针，再建一个head指针，用来寻找下一个排好序的值。必须要说，这题需要对链表这种结构的熟悉，动画片的有奖竞猜也是要看动画片的。

code

public class Solution {     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {         //做个dummy node，防止两个链表里面有空的。         ListNode dummy = new ListNode(0);         ListNode head = dummy;         //分别建两个指针，指向l1和l2，在后来可以预防链表出界。         ListNode p1 = l1;         ListNode p2 = l2;         while(p1 != null && p2 != null){             //按照大小找下一个节点。             if(p1.val < p2.val){                 head.next = p1;                 p1 = p1.next;             }             else{                 head.next = p2;                 p2 = p2.next;             }             head = head.next;         }         //最后别忘了接剩余的部分         if(p1 != null){             head.next = p1;         }         else if(p2 != null){             head.next = p2;         }         return dummy.next;     } }