程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode_Merge Two Sorted Lists

LeetCode_Merge Two Sorted Lists

編輯:關於C++

一.題目

Merge Two Sorted Lists

Total Accepted: 63974 Total Submissions: 196044My Submissions

 

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.

 

Show Tags Have you met this question in a real interview? Yes No

Discuss






二.解題技巧

這道題就是將兩個已排序的列表的元素進行比較,當某一個列表的元素比較小的話,就將其加入到輸出列表中,並將該列表的指針指向列表的下一個元素。這道題是比較簡單的,但是有一個邊界條件要注意,就是兩個列表可能會出現為空的情況,如果l1為空時,可以直接將l2進行返回;如果l2為空時,可以直接將l1返回,這樣可以減少很多計算量。

三.實現代碼

#include 

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/


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


class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        if (!l1)
        {
            return l2;
        }

        if (!l2)
        {
            return l1;
        }

        ListNode Head(0);
        ListNode *Pre = &Head;

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

        while (l1)
        {
            Pre->next = l1;
            l1 = l1->next;
            Pre = Pre->next;
        }

        while(l2)
        {
            Pre->next = l2;
            l2 = l2->next;
            Pre = Pre->next;
        }

        return Head.next;

    }
};




四.體會

這道題主要考察的就是邊界條件,主要就是處理鏈表為空的情況,也就是,如果l1為空,就返回l2,如果l2為空,就直接返回l1。簡單的題要考慮充分啊。

 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved