21.合并两个有序链表

链接：21.合并两个有序链表
难度：Easy
标签：递归、链表
简介：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题解 1 - javascript

• 编辑时间：2020-05-01
• 执行用时：84ms
• 内存消耗：35.5MB
• 编程语言：javascript
• 解法介绍：通过队列储存后排序输出。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  if (l1 === null && l2 === null) return null;
  let tmp1 = l1,
    tmp2 = l2;
  const queue = [];
  while (tmp1 !== null && tmp2 !== null) {
    if (tmp1.val <= tmp2.val) {
      queue.push(tmp1);
      tmp1 = tmp1.next;
    } else {
      queue.push(tmp2);
      tmp2 = tmp2.next;
    }
  }
  while (tmp1 !== null) {
    queue.push(tmp1);
    tmp1 = tmp1.next;
  }
  while (tmp2 !== null) {
    queue.push(tmp2);
    tmp2 = tmp2.next;
  }
  const root = queue[0];
  let tmp = root;
  for (let i = 1, len = queue.length; i < len; i++) {
    const node = queue[i] === undefined ? null : queue[i];
    tmp.next = node;
    tmp = tmp.next;
  }
  return root;
};

题解 2 - c

• 编辑时间：2021-11-30
• 执行用时：4ms
• 内存消耗：6.1MB
• 编程语言：c
• 解法介绍：新建一个头结点，遍历两个节点进行比较。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *root = (struct ListNode *)malloc(sizeof(struct ListNode)), *p = root;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            p->next = list1;
            list1 = list1->next;
        } else {
            p->next = list2;
            list2 = list2->next;
        }
        p = p->next;
    }
    if (!list1) p->next = list2;
    if (!list2) p->next = list1;
    return root->next;
}

题解 3 - cpp

• 编辑时间：2023-08-05
• 执行用时：8ms
• 内存消耗：14.5MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *head = new ListNode(), *p = head;
        while (list1 || list2) {
            if (!list2 || list1 && list1->val <= list2->val) {
                p->next = list1;
                list1 = list1->next;
            } else {
                p->next = list2;
                list2 = list2->next;
            }
            p = p->next;
        }
        return head->next;
    }
};

题解 4 - python

• 编辑时间：2023-08-05
• 执行用时：52ms
• 内存消耗：15.59MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode()
        p = head
        while list1 or list2:
            if not list2 or list1 and list1.val <= list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next
        return head.next

题解 5 - rust

• 编辑时间：2023-08-05
• 内存消耗：2.06MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
pub fn merge_two_lists(
    mut list1: Option<Box<ListNode>>,
    mut list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut head = ListNode::new(0);
    let mut p = &mut head;
    let tmp = Box::new(ListNode::new(-1));
    while list1.is_some() || list2.is_some() {
        if list2.is_none()
            || list1.is_some() && list1.as_ref().unwrap().val <= list2.as_ref().unwrap().val
        {
            let mut node = list1.take().unwrap();
            let next = node.next.take();
            p.next = Some(node);
            list1 = next;
        } else {
            let mut node = list2.take().unwrap();
            let next = node.next.take();
            p.next = Some(node);
            list2 = next;
        }
        p = p.next.as_mut().unwrap();
    }
    head.next
}
}