Linked List - Merge Two Sorted Lists

by LauCyun Sep 15,2014 22:44:33 5,991 views

Question

Problem Statement

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.

Example

Given 1->3->8->11->15->null2->null , return 1->2->3->8->11->15->null.

题解

此题为两个链表的合并,合并后的表头节点不一定,故应联想到使用dummy节点。链表节点的插入主要涉及节点next指针值的改变,两个链表的合并操作则涉及到两个节点的next值变化,若每次合并一个节点都要改变两个节点next的值且要对NULL指针做异常处理,势必会异常麻烦。

首先dummy节点还是必须要用到,除了dummy节点外还引入一个last节点充当下一次合并时的头节点。在l1或者l2的某一个节点为空指针NULL时,退出while循环,并将非空链表的头部链接到last->next中。

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Merge two sorted (ascending) linked lists and return it as a new sorted list.
 *
 * eg.
 *   Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null
 *
 * @param l1: sorted linked lists
 * @param l2: sorted linked lists
 * @return: new sorted list
 */
struct ListNode *mergeTwoSortedLists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *dummy = newNode(INT_MAX);
    struct ListNode *last = dummy;

    while ((l1 != NULL) && (l2 != NULL)) {
        if (l1->val < l2->val) {
            last->next = l1;
            l1 = l1->next;
        } else {
            last->next = l2;
            l2 = l2->next;
        }
        last = last->next;
    }

    // do not forget this line!
    last->next = (NULL != l1) ? l1 : l2;

    return dummy->next;
}

源码分析

  1. 异常处理,包含在dummy->next中。
  2. 引入dummylast节点,此时last指向的节点为dummy
  3. 对非空l1、l2循环处理,将l1、l2的较小者链接到last->next,往后递推last
  4. 最后处理l1、l2中某一链表为空退出while循环,将非空链表头链接到last->next
  5. 返回dummy->next,即最终的首指针

注意last的递推并不影响dummy->next的值,因为lastdummy是两个不同的指针变量。

Note 链表的合并为常用操作,务必非常熟练,以上的模板非常精炼,有两个地方需要记牢。1. 循环结束条件中为条件与操作;2. 最后处理last->next指针的值。

复杂度分析

最好情况下,一个链表为空,时间复杂度为\(O(1)\)。最坏情况下,last遍历两个链表中的每一个节点,时间复杂度为\( O(l1+l2)\)。 空间复杂度近似为\(O(1)\)

Tags