[LeetCode] 21. Merge Two Sorted Lists ☆

?

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.

?

解法：

　　新建一個鏈表，依次比較兩個鏈表的頭元素，把較小的移到新鏈表中，直到有一個為空，再將另一個鏈表剩余元素移到新鏈表末尾。

采用循環的方式，代碼如下：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
public class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode res = new ListNode(0);ListNode last = res;while (l1 != null && l2 != null) {if (l1.val < l2.val) {last.next = l1;l1 = l1.next;} else {last.next = l2;l2 = l2.next;}last = last.next;}last.next = (l1 != null) ? l1 : l2;return res.next;}
}

?

采用遞歸的方式，代碼如下：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
public class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;ListNode head = l1.val < l2.val ? l1 : l2;ListNode other = l1.val < l2.val ? l2 : l1;head.next = mergeTwoLists(head.next, other);return head;}
}

或者：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
public class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

?