题目

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

分析

数据结构与算法的链表章节的典型实例，将两个有序链表合成一个，保持其有序的性质。

AC代码

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        if (l1 == NULL)

            return l2;

        if (l2 == NULL)

            return l1;

        //合并后链表初始化为空

        ListNode *rl = NULL;

        ListNode *p = l1, *q = l2;

        if (l1->val <= l2->val)

        {

            rl = l1;

            p = l1->next;

        }

        else{

            rl = l2;

            q = l2->next;

        }

        rl->next = NULL;

        ListNode *head = rl;

        while (p && q)

        {

            if (p->val <= q->val)

            {

                rl->next = p;

                p = p->next;

            }

            else{

                rl->next = q;

                q = q->next;

            }//else

            rl = rl ->next;

        }//while

        while (p)

        {

            rl->next = p;

            p = p->next;

            rl = rl->next;

        }

        while (q)

        {

            rl->next = q;

            q = q->next;

            rl = rl->next;

        }

        return head;

    }

};

GitHub测试程序源码