商城网站管理系统,可以通过哪些网站注册域名,wordpress 3.6.1,创建个人网站怎么赚钱题目#xff1a; 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路
从题目和示例可以看出#xff0c;应该是要循环遍历链表进行比较#xff0c;然后组成新的链表。
第一种#xff1a;递归…题目 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路
从题目和示例可以看出应该是要循环遍历链表进行比较然后组成新的链表。
第一种递归
第二种迭代
解题过程
第一种递归
1、先判断两个链表是否为空如果list1为空则返回list2,如果list2为空则返回list1。
2、如果都不为空递归比较每个节点大小直到最后一个节点。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 null) {return list2;} else if (list2 null) {return list1;} else if (list1.val list2.val) {list1.next mergeTwoLists(list1.next, list2);return list1;} else {list2.next mergeTwoLists(list1, list2.next);return list2;}}
}
第二种迭代
1、先判断两个链表是否为空如果list1为空则返回list2 如果list2为空则返回list1。
2、其次创建新的链表作为整个链表的头部head再创建一个nextNode用于指向下一个节点比较list1和list2的每个节点将较小的节点赋值给nextNode。
3、最后返回head.next即为新的链表。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 null) {return list2;} else if (list2 null) {return list1;}ListNode head new ListNode(-1);ListNode nextNode head;while (list1 ! null list2 ! null) {if(list1.val list2.val) {nextNode.next list1;list1 list1.next; } else {nextNode.next list2;list2 list2.next; }nextNode nextNode.next;}nextNode.next list1 null ? list2 : list1;return head.next;}
}
