Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Merge Two Sorted Lists

Leetcode algorithms 第 21 题:Merge Two Sorted Lists 。

题目

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.

解答

链表归并问题。跟数组归并思路一样,使用两个链表指针逐个访问链表中的元素,并把较小者转移到总链表中,最后剩下一个链表的所有元素一次性移到总链表中。

为了处理方便,使用dummy头结点统一处理。

具体代码如下:

/**
 * 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) {
        ListNode dummy(-1), *p = &dummy;
        
        while (l1 && l2)
            if (l1->val < l2->val) //l1较小
                p->next = l1, l1 = l1->next, p = p->next;
            else                   //l2较小
                p->next = l2, l2 = l2->next, p = p->next;
        
        //l1或l2剩下的元素,直接拼接到p的后面
        if (l1) p->next = l1;
        if (l2) p->next = l2;
        
        return dummy.next;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论