网站建设做得好,名词解释 网站规划,中国建筑集团有限公司是央企吗,太原建站模板题目链接#xff1a;解题思路#xff1a;遍历#xff0c;双指针#xff1a;因为两个链表有序#xff0c;所以只需要依次比较两个元素的大小#xff0c;然后添加到新的链表中即可first指针指向第一个链表l1#xff0c;second指针指向第二个链表l2#xff0c;answer保存合…题目链接解题思路遍历双指针因为两个链表有序所以只需要依次比较两个元素的大小然后添加到新的链表中即可first指针指向第一个链表l1second指针指向第二个链表l2answer保存合并后的链表的头节点的前驱prev初值指向answer如果fist和second当前指向的节点都不为null循环遍历如果first.valsecond.valueprev.nextfirstfirstfirst.nextprevprev.next否则prev.nextsecondsecondsecond.nextprevprev.next循环结束之后那么first和second只会有一个节点不为null因为原链表已经有序所以只需要将不为null的哪个链表添加到prev.next中即可最终answer.next即所求AC代码class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode first list1;ListNode second list2;ListNode head new ListNode();ListNode tem head;while (first ! null second ! null) {if (first.val second.val) {tem.next new ListNode(first.val);first first.next;tem tem.next;} else {tem.next new ListNode(second.val);second second.next;tem tem.next;}}tem.next first ! null ? first : second;return head.next;}
}
递归解法对于递归解法首先需要定义递归函数的功能然后定义递归的终止条件递归函数mergeTwoLists(ListNode list1, ListNode list2)表示返回list1和list2有序合并之后的新链表的头节点递归的终止条件如果其中任何一个链表为null那么直接返回剩余的一个链表就可以了否则进行递归求解如果list1.vallist2.val这个时候list1就是合并后有序链表的头节点。也就是说递归函数返回的结果应该为list1但是list1后面的节点和list2还没有合并所以还不能直接返回list1返回之前需要保证list1.next的值是list1后面的节点和list2合并之后的有序链表的头节点这样list1才是满足结果的链表的头节点查看递归函数的定义经过mergeTwoLists(list.next,list2)后list.next和list2也已经有序合并并且递归函数的返回值就是list.next和list2有序合并后新链表的头节点因此list1.nextmergeTwoLists(list.next,list2)然后return list1否则合并后有序链表的头节点为list2list2.next的值就是list1和list2.next合并后有序链表的头节点因此list2.nextmergeTwoLists(list, list2.next)然后return list2AC代码class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1null){return list2;}else if (list2null){return list1;}else {if (list1.val list2.val){list1.nextmergeTwoLists(list1.next,list2);return list1;}else {list2.nextmergeTwoLists(list1,list2.next);return list2;}}}
}
