ผสานโซลูชัน Leetcode แบบเรียงลำดับสองรายการ


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน แอปเปิล บลูมเบิร์ก ทุนหนึ่ง Facebook Google ไอบีเอ็ม ไมโครซอฟท์ คำพยากรณ์
รายการที่เชื่อมโยง

รายการที่เชื่อมโยง ค่อนข้างเหมือนอาร์เรย์ในคุณสมบัติเชิงเส้น เราสามารถผสานอาร์เรย์ที่เรียงลำดับสองอาร์เรย์เพื่อสร้างอาร์เรย์ที่เรียงลำดับโดยรวม ในปัญหานี้เราต้องรวมรายการเชื่อมโยงที่เรียงลำดับสองรายการเข้าด้วยกัน ในสถานที่ เพื่อส่งคืนรายการใหม่ซึ่งมีองค์ประกอบของทั้งสองรายการในรูปแบบที่เรียงลำดับ

ตัวอย่าง

ผสานโซลูชัน Leetcode แบบเรียงลำดับสองรายการ

L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4
1 1 2 3 4 9

เข้าใกล้

วิธีที่ง่ายที่สุดคือใช้ไฟล์ สองตัวชี้ เทคนิค. สร้างรายการว่างใหม่ ต่อท้ายองค์ประกอบที่เล็กกว่าระหว่างทั้งตัวชี้และเพิ่มตัวชี้ที่เกี่ยวข้อง นี่เป็นแนวทางที่ดี แต่ต้องสร้างรายการเพิ่มเติมที่สิ้นเปลืองพื้นที่

วิธีที่เหมาะสมที่สุดควรใช้พื้นที่คงที่เท่านั้นในการทำไฟล์ ในสถานที่ การเรียงลำดับ เราสามารถทำตามวิธีการทำซ้ำ เรามีโหนดที่เก็บไว้ในทั้งสองรายการแล้ว สร้างตัวชี้รายการใหม่และตามมา“คำแนะนำต่อไป” ควรชี้ไปที่โหนดที่กำหนดไว้ล่วงหน้าในหน่วยความจำ ในกระบวนการนี้เราสร้าง ไม่ โหนดใหม่

อัลกอริทึม (วิธีไร้เดียงสา)

  1. สร้างฟังก์ชัน mergeTwoSortedLists () ที่ใช้ตัวชี้รายการสองตัวเป็นอาร์กิวเมนต์
  2. หากรายการใดรายการหนึ่งเป็น โมฆะ ส่งคืนอีกอัน
  3. สร้าง อุณหภูมิ ตัวแปรที่จะชี้ไปยังโหนดที่เล็กกว่าระหว่างส่วนหัวของทั้งสองรายการ
  4. ตอนนี้อย่างน้อยก็มีหนึ่งโหนดต่อท้ายผลลัพธ์ของเราดังนั้นควรเพิ่มหนึ่งหัว
  5. สิ่งนี้สร้างปัญหาย่อย ดังนั้นเรียกใช้ฟังก์ชันวนซ้ำเดียวกันและต่อท้ายเข้ากับ temp
  6. ถ้า List1.value <List2.value
    • อุณหภูมิ = ListNode ใหม่ (List1.value) , temp-> next = mergeTwoSortedLists (List1-> next, List2)
  7. ถ้า List2.value <= List1.value
    • อุณหภูมิ = ListNode ใหม่ (List2.value) , temp-> next = mergeTwoSortedLists (List1, List2-> next)
  8. กล้บ อุณหภูมิ เพื่อรับรายการที่ต้องการ

อัลกอริทึม (ที่เหมาะสมที่สุด)

  1. สร้างตัวชี้รายการใหม่ซึ่งจะถูกเรียก dummy_head
  2. ดูแลรักษา“พรีเฮด” (ตัวชี้คัดลอก) เพื่อให้เราสามารถเข้าถึงรายการได้ หัว ที่อยู่
  3. "คำแนะนำต่อไป” ของ dummy_head ควรจัดการในลักษณะที่ชี้ไปยังโหนดที่กำหนดไว้ล่วงหน้าในรายการ l1 และ l2.
  4. เราสามารถทำงานข้างต้นได้หลายวิธีดังต่อไปนี้:
    • ทำรายการซ้ำโดยใช้คำแนะนำเริ่มต้นจากหัวของพวกเขา
    • เว้นแต่ว่ารายการใดรายการหนึ่งจะถูกข้ามผ่านอย่างสมบูรณ์:
      • ผนวกโหนดที่มีค่าน้อยกว่าจากตัวชี้รายการทั้งสองเข้ากับ dummy_head, การเพิ่มตัวชี้ที่เกี่ยวข้อง
    • ตอนนี้อย่างน้อยหนึ่งในตัวชี้คือ เป็นโมฆะ ดังนั้นต่อท้ายไฟล์ ไม่เป็นโมฆะ รายการไปที่หัวหุ่น
  5. ส่งคืน หัว ของรายการจำลอง

การดำเนินงาน

โปรแกรม C ++ เพื่อรวมรายการที่เรียงลำดับสองรายการ

แนวทางที่ไร้เดียงสา

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;

    listNode* temp;
    if(l1->value < l2->value)
    {
        temp = new listNode(l1->value);
        temp->next = mergeTwoSortedLists(l1->next , l2);
    }
    else
    {
        temp = new listNode(l2->value);
        temp->next = mergeTwoSortedLists(l1 , l2->next);
    }

    return temp;
}


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}

วิธีที่เหมาะสมที่สุด

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
    while(l1 && l2)
    {
        if(l1->value < l2->value)
        {
            dummy_head->next = l1;
            l1 = l1->next;
        }
        else
        {
            dummy_head->next = l2;
            l2 = l2->next;
        }
        dummy_head = dummy_head->next;
    }

    dummy_head->next = (l1 ? l1 : l2);
    return prehead->next;
}



void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}
1 1 2 3 4 9

โปรแกรม Java เพื่อรวมรายการที่เรียงลำดับสองรายการ

แนวทางที่ไร้เดียงสา

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        listNode temp;
        if(l1.value < l2.value)
        {
            temp = new listNode(l1.value);
            temp.next = mergeTwoSortedLists(l1.next , l2);
        }
        else
        {
            temp = new listNode(l2.value);
            temp.next = mergeTwoSortedLists(l1 , l2.next);
        }

        return temp;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}

วิธีที่เหมาะสมที่สุด

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        listNode dummy_head = new listNode(-1) , prehead = dummy_head;
        while(l1 != null && l2 != null)
        {
            if(l1.value < l2.value)
            {
                dummy_head.next = l1;
                l1 = l1.next;
            }
            else
            {
                dummy_head.next = l2;
                l2 = l2.next;
            }
            dummy_head = dummy_head.next;
        }

        dummy_head.next = ((l1 != null) ? l1 : l2);
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}
1 1 2 3 4 9

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา เพื่อผสานสองรายการที่เรียงลำดับ

O (N + M), ที่ไหน N และ M คือความยาวของสองรายการ เราสำรวจทั้งสองรายการหนึ่งครั้งในทั้งสองวิธีดังนั้นอัลกอริทึมทั้งสองจึงเป็นเชิงเส้น

ความซับซ้อนของอวกาศ เพื่อผสานสองรายการที่เรียงลำดับ

ในแนวทางที่ดีที่สุดสิ่งสำคัญคือต้องเข้าใจว่าเราเท่านั้น จัดการตัวชี้. ดังนั้นพื้นที่คงที่สำหรับตัวแปรจึงมีไว้สำหรับการใช้หน่วยความจำ ดังนั้นวิธีการที่เหมาะสมที่สุดจึงมีความซับซ้อนของพื้นที่ O (1). O (N + M) พื้นที่ถูกใช้ในแนวทางที่ไร้เดียงสาที่กล่าวถึง