问题描述
https://leetcode.com/problems/merge-two-sorted-lists/
解决思路（2019-12-21）
- compare every value of every node in l1 and l2
- if l1.val less than l2.val, then add l1 into the new list or add l2 into the new list.
- deal with all nodes which haven’t been compared into the new list
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1. compare every value of every node in l1 and l2
//2. if l1.val less than l2.val, then add l1 into the new list
//or add l2 into the new list.
//3. deal with all nodes which haven't been compared into the
//new list
ListNode resList = new ListNode(0);
ListNode curr = resList;
//compare value and add them into new list
while(l1 != null && l2 != null){
if(l1.val < l2.val){
curr.next = l1;
l1 = l1.next;
}else{
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
//add the rest nodes into the new list
if(l1 != null){
curr.next = l1;
}
if(l2 != null){
curr.next = l2;
}
return resList.next;
}
}
解决思路（2019-06-24）
定义一个新的resList,用于保存结果。递归比较l1和l2，将结果更小者存入resList.
代码
package leetcode;
public class MergeTwoSortedLists {
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode resList;
if (l1.val < l2.val){
resList = l1;
resList.next = mergeTwoLists(l1.next, l2);
}else{
resList = l2;
resList.next = mergeTwoLists(l1, l2.next);
}
return resList;
}
}
