leetcode21：合并两个有序链表

Question

leetcode21：合并两个有序链表

sisterAn opened this issue 4 years ago · 14 comments

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

附leetcode地址：leetcode

Answer 1 · 2020-04-09T13:52:49.000Z

解答：

确定解题的数据结构： 单链表

确定解题思路： 从链表头开始比较，l1 与 l2 是有序递增的，所以比较 l1.val 与 l2.val 的较小值就是合并后链表的最小值，次小值就是小节点的 next.val 与大节点的 val 比较的较小值，依次递归，直到递归到 l1 l2 均为 null

画图实现： 画图帮助理解一下

确定边界条件： 当递归到任意链表为 null ，直接将 next 指向另外的链表即可，不需要继续递归了

代码实现：

function mergeTwoLists(l1, 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(l2.next, l1)
        return l2
    }
}

Answer 2 · 2020-04-11T10:29:08.000Z

我这个就稍微麻烦了点

var mergeTwoLists = function(l1, l2) {
    let res = new List();
    while(l1 !== null && l2 !== null){
        if(l1.element < l2.element){
            res.append(l1.element);
            l1 = l1.next;
        }else{
            res.append(l2.element);
            l2 = l2.next;
        }
    }
    let temp = !l1 ? l2 : l1;
    while(temp){
        res.append(temp.element);
        temp = temp.next;
    }
    return res;
};

Answer 3 · 2020-04-23T11:13:50.000Z

var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
    return l2
  } else if (l2 === null) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
};

Answer 4 · 2020-06-16T02:31:58.000Z

虚拟节点+ 迭代

  function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
      this.next = (next===undefined ? null : next)
 }

var mergeTwoLists = function(l1, l2) {
    
    let preHead = new ListNode(-1);
    let cur = preHead;

    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    cur.next = l1 || l2;

    return preHead.next;
};

Answer 5 · 2020-07-03T02:21:05.000Z

 const merge = (l1, l2) => {
  let temp1 = l1.head
  let temp2 = l2.head
  let list = new List()
  while (temp1 || temp2) {
    if (!temp1) {
      list.add(temp2.value)
      temp2 = temp2.next
    } else if (!temp2) {
      list.add(temp1.value)
      temp1 = temp1.next
    } else if (temp1.value >= temp2.value) {
      list.add(temp2.value)
      temp2 = temp2.next
    } else {
      list.add(temp1.value)
      temp1 = temp1.next
    }
  }
  return list
}

Answer 6 · 2020-07-15T07:22:21.000Z

function merge_link1(head1, head2) {
  if (!head1) return head2
  if (!head2) return head1

  let merge_head = null
  let merge_tail = null
  let min_data = null

  let curr1 = head1
  let curr2 = head2

  while (curr1 && curr2) {
    if (curr1.data < curr2.data) {
      min_data = curr1.data
      curr1 = curr1.next
    } else {
      min_data = curr2.data
      curr2 = curr2.next
    }

    if (!merge_head) {
      merge_head = new Node(min_data)
      merge_tail = merge_head
    } else {
      const new_node = new Node(min_data)
      merge_tail.next = new_node
      merge_tail = new_node
    }
  }

  // 循环结束后，还有某个链表还有值
  let rest_link = null
  if (curr1) {
    rest_link = curr1
  }
  if (curr2) {
    rest_link = curr2
  }

  // while (rest_link) {
  //   merge_tail.next = rest_link
  //   merge_tail = rest_link
  //   rest_link = rest_link.next
  // }
  merge_tail.next = rest_link
  return merge_head
}

Answer 7 · 2020-08-15T08:53:56.000Z

var mergeTwoLists = function(l1, l2) {
  let head = new ListNode()
  let cur = head

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1 // 指向目标节点
      l1 = l1.next // 移动到下一个节点
    } else {
      cur.next = l2
      l2 = l2.next
    }

    cur = cur.next
  } 
  // 处理l1或者l2还未遍历完的场景
  cur.next = l1 || l2

  return head.next
};

Answer 8 · 2020-09-08T16:46:36.000Z

var mergeTwoLists = function (l1, l2) {
  let p1 = new ListNode(0)
  let end = p1
  while (l1 && l2) {
    if (l1.val >= l2.val) {
      end.next = l2
      l2 = l2.next
    } else {
      end.next = l1
      l1 = l1.next
    }
    end = end.next
  }
  end.next = l1 ? l1 : l2
  return p1.next
}

Answer 9 · 2020-11-08T14:33:24.000Z

解答：

确定解题的数据结构： 单链表

确定解题思路： 从链表头开始比较，l1 与 l2 是有序递增的，所以比较 l1.val 与 l2.val 的较小值就是合并后链表的最小值，次小值就是小节点的 next.val 与大节点的 val 比较的较小值，依次递归，直到递归到 l1 l2 均为 null

画图实现： 画图帮助理解一下

确定边界条件： 当递归到任意链表为 null ，直接将 next 指向另外的链表即可，不需要继续递归了

代码实现：
function mergeTwoLists(l1, 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(l2.next, l1)
        return l2
    }
}

这个图片是用什么画图工具做出来的？

Answer 10 · 2020-11-16T14:47:56.000Z

var mergeTwoLists = function (l1, l2) {
    let prev = new ListNode();
    let p1 = l1, p2 = l2;
    let current = prev;
    while (p1 && p2) {
        if (p1.val > p2.val) {
            current.next = new ListNode(p2.val);
            p2 = p2.next;
        } else {
            current.next = new ListNode(p1.val);
            p1 = p1.next;
        }
        current = current.next;
    }
    current.next = p1 ? p1 :p2;
    return prev.next;
};

Answer 11 · 2021-03-03T05:01:20.000Z

题目地址(21. 合并两个有序链表)

https://leetcode-cn.com/problems/merge-two-sorted-lists

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

前置知识

公司

阿里
字节
腾讯
amazon
apple
linkedin
microsoft

公司

阿里、字节、腾讯

思路

本题可以使用递归来解，将两个链表头部较小的一个与剩下的元素合并，并返回排好序的链表头，当两条链表中的一条为空时终止递归。

关键点

掌握链表数据结构
考虑边界情况

代码

语言支持：CPP，JS

CPP Code:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode head, *tail = &head;
        while (a && b) {
            if (a->val <= b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }
};

JS Code:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = function (l1, 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;
  }
};

复杂度分析

M、N 是两条链表 l1、l2 的长度

时间复杂度：$O(M+N)$
空间复杂度：$O(M+N)$

扩展

你可是使用迭代的方式求解么？

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

Answer 12 · 2021-03-25T09:30:13.000Z

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  let dummy = new ListNode(null);
  let temp = dummy;
  let node1 = l1;
  let node2 = l2;
  while(node1 || node2){
    if(!node1){
      temp.next = node2;
      break;
    }
    if(!node2){
      temp.next = node1;
      break;
    }
    if(node1.val <= node2.val){
      temp.next = node1;
      node1 = node1.next;
    }else{
      temp.next = node2;
      node2 = node2.next;
    }
    temp = temp.next;
  }

  return dummy.next;
};

Answer 13 · 2021-10-01T09:03:46.000Z

/**
 * 重新创建一个链表
 */
 var mergeTwoLists = function(l1, l2) {
    if(l1===null) return l2;
    if(l2===null) return l1;
    let curL1 = l1;
    let curL2 = l2;
    let head = new ListNode(0);
    let cur = head;
    while(curL1!==null&&curL2!==null) {
        if(curL1.val<=curL2.val) {
            cur.next = curL1;
            curL1 = curL1.next;
        } else {
            cur.next = curL2;
            curL2 = curL2.next;
        }
        cur = cur.next;
    }
    cur.next = curL1===null?curL2:curL1;
    return head.next;
};

Answer 14 · 2022-12-04T04:02:44.000Z

const chain1 = {
  val: 1,
  next: {
    val: 3,
    next: {
      val: 5,
      next: null,
    },
  },
};
const chain2 = {
  val: 2,
  next: {
    val: 4,
    next: {
      val: 6,
      next: null,
    },
  },
};
function merge(l1: any, l2: any) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = merge(l1.next, l2);
    return l1;
  } else {
    l2.next = merge(l1, l2.next);
    return l2;
  }
}
merge(chain1, chain2);
console.log("chain1", chain1);
console.log("chain2", chain2);