Ex25 合并两个排序的链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

解题思路

总体解题思路比较简单。我这里用了一个小trick，就是用了一个dummy_head，来解决l1和l2同时为NULL的情况。

代码

struct ListNode *
mergeTwoLists (struct ListNode *l1, struct ListNode *l2)
{
  struct ListNode *dummy_head
      = (struct ListNode *)malloc (1 * sizeof (struct ListNode));
  dummy_head->val = -1;
  dummy_head->next = NULL;
  struct ListNode *ptr = dummy_head;
  while (l1 && l2)
    {
      if (l1->val <= l2->val)
        {
          ptr->next = l1;
          ptr = ptr->next;
          l1 = l1->next;
        }
      else
        {
          ptr->next = l2;
          ptr = ptr->next;
          l2 = l2->next;
        }
    }
  if (l1)
    {
      ptr->next = l1;
    }
  if (l2)
    {
      ptr->next = l2;
    }
  struct ListNode *ret = dummy_head->next;
  free (dummy_head);
  return ret;
}

结果

执行结果：通过

执行用时：12 ms, 在所有 C 提交中击败了89.61%的用户

内存消耗：7 MB, 在所有 C 提交中击败了27.27%的用户