forked from anishmu20/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeKsortedLists.java
More file actions
130 lines (109 loc) · 2.81 KB
/
MergeKsortedLists.java
File metadata and controls
130 lines (109 loc) · 2.81 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//Contributed by Dev jr - https://github.com/Dev-jr-8
class Solution
{
//Function to merge K sorted linked list.
//Logic for merging two sorted linked list
Node mergetwolist(Node head1, Node head2)
{
Node a = head1;
Node b = head2;
Node head = null;
Node tail = null;
if(a==null)return b;
if(b==null)return a;
if(a.data<b.data)
{
head = a;
tail = a;
a = a.next;
}
else
{
head = b;
tail = b;
b = b.next;
}
while(a!=null && b!=null)
{
if(a.data<b.data)
{
tail.next = a;
tail = a;
a = a.next;
}
else
{
tail.next = b;
tail = b;
b = b.next;
}
}
if(a==null)tail.next=b;
if(b==null)tail.next=a;
return head;
}
Node mergeKList(Node[]arr,int K)
{
//Add your code here.
Node ans = null;
//Taking pair of sorted linked list and merging them, Storing their start point(head)
//in ans reference variable
for(Node i : arr)
{
ans = mergetwolist(i,ans);
}
return ans;
}
//Time Complexity : o(n^2)
//Space Complexity : o(1)
}
//geeksforgeeks driver code
//{ Driver Code Starts
import java.util.*;
class Node
{
int data;
Node next;
Node(int key)
{
data = key;
next = null;
}
}
class GfG
{
public static void printList(Node node)
{
while(node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0)
{
int N = sc.nextInt();
Node []a = new Node[N];
for(int i = 0; i < N; i++)
{
int n = sc.nextInt();
Node head = new Node(sc.nextInt());
Node tail = head;
for(int j=0; j<n-1; j++)
{
tail.next = new Node(sc.nextInt());
tail = tail.next;
}
a[i] = head;
}
Solution g = new Solution();
Node res = g.mergeKList(a,N);
if(res!=null)
printList(res);
System.out.println();
}
}
}