题目:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
题解:
这道题是链表操作题,题解方法很直观。
首先,进行边界条件判断,如果任一一个表是空表,就返回另外一个表。
然后,对于新表选取第一个node,选择两个表表头最小的那个作为新表表头,指针后挪。
然后同时遍历两个表,进行拼接。
因为表已经是sorted了,最后把没有遍历完的表接在新表后面。
由于新表也会指针挪动,这里同时需要fakehead帮助记录原始表头。
代码如下:
1 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 2 if(l1== null) 3 return l2; 4 if(l2== null) 5 return l1; 6 7 ListNode l3; 8 if(l1.val<l2.val){ 9 l3 = l1; 10 l1 = l1.next; 11 } else{ 12 l3 = l2; 13 l2 = l2.next; 14 } 15 16 ListNode fakehead = new ListNode(-1); 17 fakehead.next = l3; 18 while(l1!= null&&l2!= null){ 19 if(l1.val<l2.val){ 20 l3.next = l1; 21 l3 = l3.next; 22 l1 = l1.next; 23 } else{ 24 l3.next = l2; 25 l3 = l3.next; 26 l2 = l2.next; 27 } 28 } 29 30 if(l1!= null) 31 l3.next = l1; 32 if(l2!= null) 33 l3.next = l2; 34 return fakehead.next; 35 }
更简便的方法是,不需要提前选新表表头。
对于新表声明两个表头,一个是fakehead,一个是会挪动的指针,用于拼接。同时,边界条件在后面的补拼中页解决了,所以开头没必要做边界判断,这样代码简化为:
1 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 2 ListNode fakehead = new ListNode(-1); 3 ListNode l3 = fakehead; 4 while(l1!= null&&l2!= null){ 5 if(l1.val<l2.val){ 6 l3.next = l1; 7 l3 = l3.next; 8 l1 = l1.next; 9 } else{ 10 l3.next = l2; 11 l3 = l3.next; 12 l2 = l2.next; 13 } 14 } 15 16 if(l1!= null) 17 l3.next = l1; 18 if(l2!= null) 19 l3.next = l2; 20 return fakehead.next; 21 }