← Back to DSA Course | Chapter 4: Linked Lists | Lesson 6 of 8

दो Sorted Lists को Merge करना

दो sorted lists merge करना height से sorted kids की दो lines को एक में combine करने जैसा है, हमेशा हर line के front से छोटे वाले को picking करते हुए।

In this page:

  1. Problem
  2. Merge Process
  3. Remaining Nodes
  4. Result
  5. Complexity
Syntax
markup 
dummy = tail = Node(0)
while l1 and l2:
    if l1.data <= l2.data:
        tail.next, l1 = l1, l1.next
    else:
        tail.next, l2 = l2, l2.next
    tail = tail.next
tail.next = l1 or l2
return dummy.next

Problem

दो linked lists दिए जाने पर जो हर एक पहले से sorted हैं, उन्हें बिना कुछ भी पूरी तरह re-sort किए एक single sorted list में combine किया जा सकता है, दो current front values में से छोटे को बार-बार picking करके।

उदाहरण: Problem

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* l1 = new Node{1, new Node{3, new Node{5, nullptr}}};
    Node* l2 = new Node{2, new Node{4, nullptr}};
    cout << "list1: 1 3 5, list2: 2 4 -- both already sorted" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node l1 = new Node(1); l1.next = new Node(3); l1.next.next = new Node(5);
        Node l2 = new Node(2); l2.next = new Node(4);
        System.out.println("list1: 1 3 5, list2: 2 4 -- both already sorted");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

l1 = Node(1); l1.next = Node(3); l1.next.next = Node(5)
l2 = Node(2); l2.next = Node(4)
print("list1: 1 3 5, list2: 2 4 -- both already sorted")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
    l1->next = malloc(sizeof(struct Node)); l1->next->data = 3;
    l1->next->next = malloc(sizeof(struct Node)); l1->next->next->data = 5; l1->next->next->next = NULL;
    printf("list1: 1 3 5 -- already sorted\n");
    return 0;
}

Merge Process

हर step पर, दोनों lists के current node compare करें और जिसमें भी छोटी value हो उसे result से attach करें, फिर सिर्फ उस list के pointer को इसके अगले node तक आगे बढ़ाएं।

उदाहरण: Merge Process

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* l1 = new Node{1, new Node{3, nullptr}};
    Node* l2 = new Node{2, new Node{4, nullptr}};
    Node dummy{0, nullptr}; Node* tail = &dummy;
    while (l1 && l2) {
        if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    for (Node* c = dummy.next; c; c = c->next) cout << c->data << " ";
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node l1 = new Node(1); l1.next = new Node(3);
        Node l2 = new Node(2); l2.next = new Node(4);
        Node dummy = new Node(0); Node tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.data < l2.data) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        for (Node c = dummy.next; c != null; c = c.next) System.out.print(c.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

l1 = Node(1); l1.next = Node(3)
l2 = Node(2); l2.next = Node(4)
dummy = Node(0)
tail = dummy
while l1 and l2:
    if l1.data < l2.data:
        tail.next = l1; l1 = l1.next
    else:
        tail.next = l2; l2 = l2.next
    tail = tail.next
c = dummy.next
while c:
    print(c.data, end=" ")
    c = c.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
    l1->next = malloc(sizeof(struct Node)); l1->next->data = 3; l1->next->next = NULL;
    struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
    l2->next = malloc(sizeof(struct Node)); l2->next->data = 4; l2->next->next = NULL;
    struct Node dummy = {0, NULL}; struct Node *tail = &dummy;
    while (l1 && l2) {
        if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    for (struct Node *c = dummy.next; c; c = c->next) printf("%d ", c->data);
    return 0;
}

Remaining Nodes

एक बार दो lists में से एक के nodes खत्म हो जाएं, compare करते रहने की ज़रूरत नहीं: दूसरी list का बाकी हिस्सा पहले से sorted है, इसलिए इसे बस result के आखिर में wholesale attach किया जा सकता है।

उदाहरण: Remaining Nodes

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* l1 = nullptr;
    Node* l2 = new Node{2, new Node{4, new Node{6, nullptr}}};
    Node dummy{0, nullptr}; Node* tail = &dummy;
    tail->next = l1 ? l1 : l2;
    cout << "list1 exhausted, remainder of list2 attached wholesale: ";
    for (Node* c = tail->next; c; c = c->next) cout << c->data << " ";
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node l1 = null;
        Node l2 = new Node(2); l2.next = new Node(4); l2.next.next = new Node(6);
        Node dummy = new Node(0);
        dummy.next = (l1 != null) ? l1 : l2;
        System.out.print("list1 exhausted, remainder of list2 attached wholesale: ");
        for (Node c = dummy.next; c != null; c = c.next) System.out.print(c.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

l1 = None
l2 = Node(2); l2.next = Node(4); l2.next.next = Node(6)
dummy = Node(0)
dummy.next = l1 if l1 else l2
print("list1 exhausted, remainder of list2 attached wholesale: ", end="")
c = dummy.next
while c:
    print(c.data, end=" ")
    c = c.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *l1 = NULL;
    struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
    l2->next = malloc(sizeof(struct Node)); l2->next->data = 4; l2->next->next = NULL;
    struct Node dummy = {0, NULL};
    dummy.next = l1 ? l1 : l2;
    printf("remainder attached wholesale: ");
    for (struct Node *c = dummy.next; c; c = c->next) printf("%d ", c->data);
    return 0;
}

Result

चूंकि हर original node merged result में copy होने के बजाय reuse होता है, और हर step पर दोनों current values में से छोटी चुनी जाती है, final list की guarantee है कि यह पूरी तरह sorted रहे।

उदाहरण: Result

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* merge(Node* l1, Node* l2) {
    Node dummy{0, nullptr}; Node* tail = &dummy;
    while (l1 && l2) {
        if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}
int main() {
    Node* l1 = new Node{1, new Node{4, nullptr}};
    Node* l2 = new Node{2, new Node{3, nullptr}};
    for (Node* c = merge(l1, l2); c; c = c->next) cout << c->data << " ";
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static Node merge(Node l1, Node l2) {
        Node dummy = new Node(0); Node tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.data < l2.data) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
    public static void main(String[] args) {
        Node l1 = new Node(1); l1.next = new Node(4);
        Node l2 = new Node(2); l2.next = new Node(3);
        for (Node c = merge(l1, l2); c != null; c = c.next) System.out.print(c.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def merge(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2
    return dummy.next

l1 = Node(1); l1.next = Node(4)
l2 = Node(2); l2.next = Node(3)
c = merge(l1, l2)
while c:
    print(c.data, end=" ")
    c = c.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* merge(struct Node *l1, struct Node *l2) {
    struct Node dummy = {0, NULL}; struct Node *tail = &dummy;
    while (l1 && l2) {
        if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}
int main() {
    struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
    l1->next = malloc(sizeof(struct Node)); l1->next->data = 4; l1->next->next = NULL;
    struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
    l2->next = malloc(sizeof(struct Node)); l2->next->data = 3; l2->next->next = NULL;
    for (struct Node *c = merge(l1, l2); c; c = c->next) printf("%d ", c->data);
    return 0;
}

Complexity

Merging O(n+m) time में खत्म होती है, दोनों lists के हर node को बिल्कुल एक बार visit करते हुए, और input lists से आगे सिर्फ O(1) extra space चाहिए, क्योंकि यह नए nodes allocate करने के बजाय बस मौजूदा nodes को relink करती है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* merge(Node* l1, Node* l2) {
    Node dummy{0, nullptr}; Node* tail = &dummy;
    while (l1 && l2) {
        if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}
int main() {
    Node* l1 = new Node{1, new Node{4, nullptr}};
    Node* l2 = new Node{2, new Node{3, nullptr}};
    merge(l1, l2);
    cout << "O(n+m) time, O(1) space -- nodes relinked, not copied" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static Node merge(Node l1, Node l2) {
        Node dummy = new Node(0); Node tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.data < l2.data) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
    public static void main(String[] args) {
        Node l1 = new Node(1); l1.next = new Node(4);
        Node l2 = new Node(2); l2.next = new Node(3);
        merge(l1, l2);
        System.out.println("O(n+m) time, O(1) space -- nodes relinked, not copied");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def merge(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2
    return dummy.next

l1 = Node(1); l1.next = Node(4)
l2 = Node(2); l2.next = Node(3)
merge(l1, l2)
print("O(n+m) time, O(1) space -- nodes relinked, not copied")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* merge(struct Node *l1, struct Node *l2) {
    struct Node dummy = {0, NULL}; struct Node *tail = &dummy;
    while (l1 && l2) {
        if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}
int main() {
    struct Node *l1 = malloc(sizeof(struct Node)); l1->data = 1;
    l1->next = malloc(sizeof(struct Node)); l1->next->data = 4; l1->next->next = NULL;
    struct Node *l2 = malloc(sizeof(struct Node)); l2->data = 2;
    l2->next = malloc(sizeof(struct Node)); l2->next->data = 3; l2->next->next = NULL;
    merge(l1, l2);
    printf("O(n+m) time, O(1) space\n");
    return 0;
}
Related Topics

K Sorted Lists को Merge करना · Merge Sort क्या है · Two Pointer तकनीक · Two Sum समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Loop के बाद non-empty list के बचे हुए nodes attach करना भूल जाना, इसलिए एक list का tail खो जाता है।
  2. हर value के लिए नए nodes बनाकर result बनाना जब आप मौजूदा nodes relink कर सकते थे, extra memory उपयोग करते हुए।
  3. एक dummy head node उपयोग न करना, इसलिए first-node case को special handling चाहिए और अक्सर एक empty list पर crash होती है।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Floyds Cycle Detection Next Lesson → Find Middle of Linked List

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.