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

leetcode筆記:Merge Two Sorted Lists

編輯:C++入門知識

leetcode筆記: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.

二.題目分析

這道題題意是,將兩個已排序的鏈表的各個元素進行比較並合並成一個鏈表,具體思路是,當某一個列表的元素比較小的話,就將其加入到輸出鏈表中,並將該鏈表的指針指向鏈表的下一個元素。題目需要注意邊界條件,即兩個鏈表可能會出現為空的情況,如果p1為空時,可以直接將p2進行返回;如果p2為空時,可以直接將p1返回,這樣可以減少一些計算量。

三.示例代碼

#include 

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


class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* p1, ListNode* p2)
    {
        if (!p1) return p2;
        if (!p2) return p1;

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

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

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

        while (p2)
        {
            Pre->next = p2;
            p2 = p2->next;
            Pre = Pre->next;
        }
        return Head.next;
    }
};

四.小結

這道題主要考察的是鏈表的基本操作和一些隱藏的邊界條件,越是簡單的問題越要考慮充分。

 

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