Wednesday, September 28, 2022

Merge 2 sorted linked list in reverse order

Given two linked lists of size N and M, which are sorted in non-decreasing order. The task is to merge them in such a way that the resulting list is in decreasing order.

Input:
First line of input contains number of testcases T. For each testcase, first line of input contains length of both linked lists N and M respectively. Next two lines contains N and M elements of two linked lists.

Output:
For each testcase, print the merged linked list which is in non-increasing order.

User Task:
The task is to complete the function mergeResult() which takes reference to the heads of both linked list and returns the pointer to the merged linked list.

Constraints:
1 <=T<= 50
1 <= N, M <= 1000

Example:
Input:

2
4 3
5 10 15 40 
2 3 20
2 2
1 1
2 4

Output:
40 20 15 10 5 3 2
4 2 1 1 

Explanation:
Testcase 1:
 After merging the two lists in decreasing order, we have new lists as 40->20->15->10->5->3->2.


My Answer:

    Node mergeResult(Node node1, Node node2)
    {
	    ArrayList<Integer> arrayList = new ArrayList<>();
	    while( node1 != null || node2 != null) {
                if( node1 == null ) {
                    arrayList.add(node2.data);
                    node2 = node2.next;
                } else if( node2 == null ) {
                    arrayList.add(node1.data);
                    node1 = node1.next;
                } else if ( node1.data <= node2.data ) {
	                arrayList.add(node1.data);
	                node1 = node1.next;
	        } else {
	            arrayList.add(node2.data);
	            node2 = node2.next;
	        }
	    }
	    
	    Node node = new Node(arrayList.get(arrayList.size()-1));
	    Node prevNode = node;
	    for (int i = arrayList.size()-2; i >= 0 ; i-- ) {
	        Node nextNode = new Node(arrayList.get(i));
	        prevNode.next = nextNode;
	        prevNode = nextNode;
	    }
	    
	    return node;
    }

No comments:

Post a Comment

Search in a matrix

  Problem: Given a matrix  mat [][] of size  N  x  M , where every row and column is sorted in increasing order, and a number  X  is given. ...