Ayoub Ali

Posted on

Merge Two Sorted Lists Solution in Dart

Question

Question

You are given the heads of two sorted linked lists, list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

Solution

All Solutions are working perfectly in the terminal but one solution taking more time to execute because of maybe two while loop, but it completes the all testes.

I divided my solution into A, B, C, D rather than Solution as defined in the question section
because I have many solutions, so I can not give same name to every class, so I write them as A, B, C, D which you can change if you want

Node Class

``````class ListNode {
int val;
ListNode? next;
ListNode([this.val = 0, this.next]);
}
``````

First Solution

``````class A {
ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
if (list1 == null)
return list2;
else if (list2 == null) return list1;

ListNode res = ListNode(-1);
if (list1.val < list2.val) {
res.next = list1;
list1 = list1.next;
} else {
res.next = list2;
list2 = list2.next;
}
ListNode? ptr = res.next;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
ptr?.next = list1;
ptr = ptr?.next;
list1 = list1.next;
} else {
ptr?.next = list2;
ptr = ptr?.next;
list2 = list2.next;
}
}
while (list1 != null) {
ptr?.next = list1;
ptr = ptr?.next;
list1 = list1.next;
}
while (list2 != null) {
ptr?.next = list2;
ptr = ptr?.next;
list2 = list2.next;
}
return res.next;
}

/*

Runtime: 361 ms, faster than 100.00% of Dart online submissions for Merge Two Sorted Lists.
Memory Usage: 143.5 MB, less than 100.00% of Dart online submissions for Merge Two Sorted Lists.

*/
}

``````

Second Solution

``````class B {
// 208 / 208 test cases passed, but took too long.

ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
List<int>? listMerged = <int>[];

while (list1 != null) {
list1 = list1.next;
}

while (list2 != null) {
list2 = list2.next;
}

listMerged.sort();

for (var i in listMerged) {
}

}
}

``````

Third Solution

A little bit documentation

``````
class C {
// in Node List we have two things one is head which always at
// the first and tail which always at the end.

ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
// checking if the first list value is empty if  it is than we will return the value of the another
// list and vice versa
if (list1 == null)
return list2;
else if (list2 == null) return list1;

// to store the values of the two lists in another ListNode variable
ListNode? temp1 = list1;
ListNode? temp2 = list2;

// while both are not null  like if we don't enter the null values
while (temp1 != null && temp2 != null) {
// and if the first value is larger than the second in a nodeList
if (temp1.val > temp2.val) {
// than we will insert the second nodeList value first because
// as written in the question we also have to arrange the values
insertNode(temp2.val);
// than second nodeValue will be our next value
temp2 = temp2.next;
} else {
// if it is  not larger than we will use this condition
// smaller will will always say at first
insertNode(temp1.val);
temp1 = temp1.next;
}
}
// condition if we don't enter the null values
// than we will set the next value of both nodes into the nodeList
if (temp1 != null) tail?.next = temp1;
if (temp2 != null) tail?.next = temp2;
}

void insertNode(int val) {
//  than we will insert the node and set it values
ListNode node = ListNode(val);
else {
tail?.next = node;
tail = node;
}
}

/*

Runtime: 429 ms, faster than 100.00% of Dart online submissions for Merge Two Sorted Lists.
Memory Usage: 143.8 MB, less than 100.00% of Dart online submissions for Merge Two Sorted Lists.

*/
}
``````

Fourth Solution

``````class D {
ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
if (list1 == null) {
return list2;
}

if (list2 == null) {
return list1;
}
if (list1.val > list2.val) {
list2 = list2.next;
} else {
list1 = list1.next;
}

while (list1 != null && list2 != null) {
if (list1.val > list2.val) {
current?.next = list2;
list2 = list2.next;
} else {
current?.next = list1;
list1 = list1.next;
}
current = current?.next;
}

if (list1 == null) {
current?.next = list2;
}
if (list2 == null) {
current?.next = list1;
}