Created
July 1, 2022 15:37
-
-
Save yoosinpaddy/e9b0daca2c2c219434d8532d1109a7e8 to your computer and use it in GitHub Desktop.
Merge two linked list of integers in ascending order
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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