Skip to content

Instantly share code, notes, and snippets.

@yoosinpaddy
Created July 1, 2022 15:37
Show Gist options
  • Save yoosinpaddy/e9b0daca2c2c219434d8532d1109a7e8 to your computer and use it in GitHub Desktop.
Save yoosinpaddy/e9b0daca2c2c219434d8532d1109a7e8 to your computer and use it in GitHub Desktop.
Merge two linked list of integers in ascending order
package com.company;
import java.io.*;
import java.util.*;
public class Solution {
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
}
public static void printSinglyLinkedList(SinglyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));
node = node.next;
if (node != null) {
bufferedWriter.write(sep);
}
}
}
// Complete the mergeLists function below.
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode next;
* }
*
*/
static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
List<Integer> allDetails= new ArrayList<>();
allDetails.add(head1.data);
allDetails.add(head2.data);
while (head1.next!=null){
allDetails.add(head1.next.data);
head1=head1.next;
}
while (head2.next!=null){
allDetails.add(head2.next.data);
head2=head2.next;
}
Collections.sort(allDetails);
System.out.println(Arrays.toString(allDetails.toArray()));
SinglyLinkedListNode mStart = new SinglyLinkedListNode(allDetails.get(0));
SinglyLinkedListNode mCopy = mStart;
for (int i = 1; i < allDetails.size(); i++) {
mCopy.next= new SinglyLinkedListNode(allDetails.get(i));
mCopy=mCopy.next;
System.out.println("Position:"+allDetails.get(i));
}
return mStart;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = null;
try {
File f = new File("s.txt");
if (!f.exists()) {
System.out.println(f.createNewFile());
}
bufferedWriter = new BufferedWriter(new FileWriter(f.getName()));
} catch (IOException e) {
e.printStackTrace();
}
int tests = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int testsItr = 0; testsItr < tests; testsItr++) {
SinglyLinkedList llist1 = new SinglyLinkedList();
int llist1Count = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < llist1Count; i++) {
int llist1Item = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
llist1.insertNode(llist1Item);
}
SinglyLinkedList llist2 = new SinglyLinkedList();
int llist2Count = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < llist2Count; i++) {
int llist2Item = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
llist2.insertNode(llist2Item);
}
SinglyLinkedListNode llist3 = mergeLists(llist1.head, llist2.head);
printSinglyLinkedList(llist3, " ", bufferedWriter);
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment