Sort an array of 0s, 1s and 2s | Dutch National Flag problem

Sort an array of 0s, 1s and 2s |

Dutch National Flag problem

👀👀👀👀👀

/*

* This program defines a sortArray() method that sorts

* an array of 0s, 1s, and 2s using

* the Dutch National Flag algorithm.

*/

public class Sort012 {

public static void swap(int[] arr,int i,int j) {

int temp;

temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

public static void sortArray(int[] arr) {

int low =0;

int mid =0;

int high =arr.length-1;

while(mid<=high) {

switch (arr[mid]) {

case 0:

swap(arr,low,mid);

low++;

mid++;

break;

case 1:

mid++;

break;

case 2:

swap(arr,mid,high);

high--;

break;

default:

break;

}

}

}

public static void main(String... aa) {

int arr[]= {2,0,1,0,2,1,2,0,1,0,2,1};

sortArray(arr);

for(int i:arr) {

System.out.print(i+" ");

}

}

}

Output:

0 0 0 0 1 1 1 1 2 2 2 2

Merge two sorted linked lists

public class MergeLinkedLists {

static class ListNode {

int val;

ListNode next;

public ListNode() {}

public ListNode(int val) {

this.val = val;

}

public ListNode(int val, ListNode next) {

this.val = val;

this.next = next;

}

}

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

ListNode mergedList = new ListNode();

ListNode current = mergedList;

while (list1 != null && list2 != null) {

if (list1.val <= list2.val) {

current.next = list1;

list1 = list1.next;

} else {

current.next = list2;

list2 = list2.next;

}

current = current.next;

}

if (list1 != null) {

current.next = list1;

} else {

current.next = list2;

}

return mergedList.next;

}

public static void main(String[] args) {

// Example usage:

ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(4)));

ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));

ListNode mergedList = mergeTwoLists(list1, list2);

while (mergedList != null) {

System.out.print(mergedList.val + " ");

mergedList = mergedList.next;

}

}

}

Time Complexity: O(M + N), Where M and N are the size of the list1 and list2 respectively.
Auxiliary Space: O(M+N), Function call stack space

Output:

1 1 2 3 4 4

Geeks link:

    Merge To Linked List