合并两个有序链表 Merge Two Sorted Lists

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const mergeTwoLists = function(l1, l2) {
  if(!l1){
    return l2;
  }

  if(!l2){
    return l1;
  }

  if(l1.val < l2.val){
    l1.next = mergeTwoLists(l1.next, l2);

    return l1;
  }
  else{
    l2.next = mergeTwoLists(l1, l2.next);

    return l2;
  }
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const mergeTwoLists = function(l1, l2) {
  if(!l1 || !l2){
    return getRest(l1,l2);
  }

  let fakeHead = new ListNode(-1);
  let currentNode = fakeHead;

  while(l1 && l2){
    let l1IsSmaller = l1.val < l2.val;
    let newNode = l1IsSmaller ? new ListNode(l1.val) : new ListNode(l2.val);
    currentNode.next = newNode;
    currentNode = newNode;
    if(l1IsSmaller){
      l1 = l1.next;
    }
    else{
      l2 = l2.next;
    }
  }
  currentNode.next = getRest(l1,l2);
  return fakeHead.next;
};

function getRest(l1,l2){
  return !!l1 ? l1 : l2;
}