Leetcode Merge Two Sorted Lists

Python publisher01 38℃

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

算法的基本思路是:
对两个有序列表取第一个元素比较,选取小的那个节点,放到当前列表中,移动指针。
最后把剩下的较长的列表合并到结果列表中。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
  if (l1 == NULL) {
    return l2;
  }
  if (l2 == NULL) {
    return l1;
  }
  // 使用一个哑节点
  struct ListNode* dummy_node;
  dummy_node = malloc(sizeof(struct ListNode));
  dummy_node->next = NULL;
  dummy_node->val = 0;
  // 待返回的表头
  struct ListNode* ret = dummy_node;
  struct ListNode* temp1 = l1;
  struct ListNode* temp2 = l2;
  struct ListNode* new_node;
  while (temp1 && temp2) {
    new_node = malloc(sizeof(struct ListNode));
    new_node->next = NULL;
    if (temp1->val <= temp2->val) {
      new_node->val = temp1->val;
      temp1 = temp1->next;
    } else {
      new_node->val = temp2->val;
      temp2 = temp2->next;
    }
    dummy_node->next = new_node;
    dummy_node = new_node;
  }
  // 把多的出来的节点加进来
  if (temp1) {
    dummy_node->next = temp1;
  }
  if (temp2) {
    dummy_node->next = temp2;
  }
  return ret->next;
}

合并两个有序list,思路基本一致,Python实现:

a = [12,45,64,100]
b = [11,42,321,1000,9999]
def meger_list(a, b):
  ret = []
  while a and b:
    if a[0] <= b[0]:
      ret.append(a.pop(0))
    else:
      ret.append(b.pop(0))
  if a:
    ret.extend(a)
  if b:
    ret.extend(b)
  return ret
if __name__ == '__main__':
  print(meger_list(a, b))

转载请注明:Python量化投资 » Leetcode Merge Two Sorted Lists

喜欢 (0)or分享 (0)