• Register
Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Merge two sorted linked list in reverse order

0 votes
30 views
Merge two sorted linked list in reverse order.
List1: [5 10 15 20 40 ]
List2: [2 3 20 ]
resutl List: [40 20 15 10 5 3 2 ]
asked Feb 8 in Data Structure And Algorithm by Dev

2 Answers

0 votes
Following running example for merging two sorted list. If you want to merge two sorted linked list in reverse order then follow the following steps:-
Step1:- Iterate both linked list and check not null
Step2:- If list1 data is less than list2 data then
    2.1:- Create a new node with list1 data
    2.2:- And move into next node of list1
    2.3:- Call addMergeNodeInReverseOrder() method for adding node into final merged list. This function always add new node in first position
Step3:- Else If list1 data is getter than list2 data then
    3.1:- Create a new node with list2 data
    3.2:- And move into next node of list2
    3.3:- Call addMergeNodeInReverseOrder() method for adding node into final merged list.
Step4:- If list1 data and list2 data are same then
    4.1:- Create a new node with list1 data
    4.2:- And move into next node of list1 and list2
    4.3:- Call addMergeNodeInReverseOrder() method for adding node into final merged list.
Step5:- Add remaining nodes of list1 and list2

package com.ds.linkedlist;

public class MergeSortedList {
    private Node head;
    public static void main(String[] args) {
        MergeSortedList sp1 = new MergeSortedList();
        sp1.insert(5);
        sp1.insert(10);
        sp1.insert(15);
        sp1.insert(20);
        sp1.insert(40);
        Node list1 = sp1.getHead();
        System.out.print("\nList1: ");
        sp1.print(list1);

        MergeSortedList sp2 = new MergeSortedList();
        sp2.insert(2);
        sp2.insert(3);
        sp2.insert(20);
        Node list2 = sp2.getHead();
        System.out.print("\nList2: ");
        sp2.print(list2);

        System.out.print("\nMerged List In Reverse Order: ");
        Node mlistInReverseOrder = sp2.getMergedSortedListInReverseOrder(list1, list2);
        sp2.print(mlistInReverseOrder);
    }

    //Function merge two sorted linked list in reverse order
    public Node getMergedSortedListInReverseOrder(Node list1, Node list2){
        Node mlist = null;
        Node newNode = null;
        while(list1 != null && list2 != null){
            if(list1.data < list2.data){
                newNode = new Node(list1.data);
                list1 = list1.next;
            }else if(list1.data > list2.data){
                newNode = new Node(list2.data);
                list2 = list2.next;
            }else{
                newNode = new Node(list1.data);
                list1 = list1.next;
                list2 = list2.next;
            }
            mlist = addMergeNodeInReverseOrder(newNode,mlist);
        }
        while(list1 != null){
            newNode = new Node(list1.data);
            mlist = addMergeNodeInReverseOrder(newNode,mlist);
            list1 = list1.next;
        }
        while(list2 != null){
            newNode = new Node(list2.data);
            mlist = addMergeNodeInReverseOrder(newNode,mlist);
            list2 = list2.next;
        }
        return mlist;
    }

    //Add first node
    private Node addMergeNodeInReverseOrder(Node newNode, Node mlist) {
        newNode.next = mlist;
        return newNode;
    }

    private class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }

    public Node getHead(){
        return this.head;
    }

    public void insert(int data){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
        }else{
            Node curr = head;
            while(curr.next != null){
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }

    public void print(Node node){
        if(node==null)
            return;
        Node curr = node;
        while(curr != null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
    }

}
Output:-
List1: 5 10 15 20 40
List2: 2 3 20
Merged List In Reverse Order: 40 20 15 10 5 3 2
answered Feb 9 by me_vinod12 (1,960 points)
0 votes
See the following running example to merge two sorted linked list in reverse order.

Following steps:-
Step1:- Iterate both linked list and check not null
Step2:- If list1 data is less than list2 data then
    2.1:- Save next node of list1 in temp.
    2.2:- Set list1 next with merged list (mlist)
    2.3:- Finally assigned mlist with list1
    2.4:- And move next node of list1 with assigning temp data
Step3:- Else If list1 data is getter than list2 data then
    3.1:- Save next node of list2 in temp.
    3.2:- Set list2 next with merged list (mlist)
    3.3:- Finally assigned mlist with list2
    3.4:- And move next node of list2 with assigning temp data
Step4:- If list1 data and list2 data are same then
    4.1:- Save next node of list1 in temp.
    4.2:- Set list1 next with merged list (mlist)
    4.3:- Finally assigned mlist with list1
    4.2:- And move into next node of list1 and list2  
Step5:- Add remaining nodes of list1 and list2 into mlist


private Node getMergedSortedListInReverse(Node list1, Node list2) {
        Node mlist = null;
        while(list1 != null && list2 != null){
            if(list1.data < list2.data){
                Node temp = list1.next;
                list1.next = mlist;
                mlist = list1;
                list1 = temp;
            }else if(list2.data < list1.data){
                Node temp = list2.next;
                list2.next = mlist;
                mlist = list2;
                list2 = temp;
            }else{
                Node temp = list1.next;
                list1.next = mlist;
                //Adding only equal one node
                mlist = list1;
                list1 = temp;

                //Jump next node in second list
                list2 = list2.next;
            }
        }
        // Add remaining nodes of first list at the front of result list
        // If second list reached end, but first list having some more nodes
        while(list1 != null){
            Node temp = list1.next;
            list1.next = mlist;
            mlist = list1;
            list1 = temp;
        }
        // Add remaining nodes of second list at the front of result list
        // If first list reached end, but second list having some more nodes
        while(list2 != null){
            Node temp = list2.next;
            list2.next = mlist;
            mlist = list2;
            list2 = temp;
        }
        return mlist;
    }
answered Feb 9 by ranju_12 (2,280 points)
...