Merge two sorted lists java

LeetCode – Merge Two Sorted Lists (Java)

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Java Solution

The key to solve the problem is defining a fake head. Then compare the first elements from each list. Add the smaller one to the merged list. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); ListNode p=head; ListNode p1=l1; ListNode p2=l2; while(p1!=null && p2!=null){ if(p1.val  p2.val){ p.next = p1; p1 = p1.next; }else{ p.next = p2; p2 = p2.next; } p=p.next; } if(p1!=null){ p.next = p1; } if(p2!=null){ p.next = p2; } return head.next; }

Related posts:

If you want someone to read your code, please put the code inside

 and 

tags. For example:

Hi. I know about reference types but I don’t understand how `head` get its value. what topics should I read about to know how its works?

Why to use break; ?? because we can have more than one value in first linked list as compared to other. example L1= 1 ,2, 6 ,4 ,5. l2= 5,3,9

code has mistake
correct code
in
else if(l1==null) p.next = l2;
l2 = l2.next;
p = p.next;
break;
>
else if(l2==null) p.next = l1;
l1 = l1.next;
p = p.next;
break;
>

Thanks, much simple solution.
using recursion space complexity is O(n).
space complexity O(1) would be much better.

I liked the core of your solution of creating a fakehead. But, unfortunately it is not complete. Below is the complete non-recursive solution for the above problem in JAVA:
public class MergingTwoSortedLists < private class ListNode int val;
ListNode next;
ListNode(int x) < val = x; >
> ListNode head1;
ListNode head2; public ListNode mergeTwoLists(ListNode l1, ListNode l2) ListNode list1 = l1;
ListNode list2 = l2; ListNode head = new ListNode(0);
ListNode merged = head; if(l1 == null && l2 != null) return l2;
> if(l1 != null && l2 == null) return l1;
> while(list1 != null && list2 != null) if(list1.val < list2.val)merged.next = list1;
list1 = list1.next;
>
else merged.next = list2;
list2 = list2.next;
>
merged = merged.next;
>
//If list1 alone is present
while(list1 != null) merged.next = list1;
list1 = list1.next;
merged = merged.next;
> //If list2 alone is present
while(list2 != null) merged.next = list2;
list2 = list2.next;
merged = merged.next;
>
return head.next;
> public void display(ListNode head) ListNode temp = head;
while(temp != null) System.out.print(temp.val+» «);
temp = temp.next;
>
System.out.println();
> public static void main(String[] args) MergingTwoSortedLists obj = new MergingTwoSortedLists();
obj.head1 = obj.new ListNode(1);
obj.head1.next = obj.new ListNode(3);
obj.head2 = obj.new ListNode(2);
obj.head2.next = obj.new ListNode(4);
obj.display(obj.head1);
obj.display(obj.head2);
obj.display(obj.mergeTwoLists(obj.head1,obj.head2)); >
>

for me recursion worked :- public static Node mergeLists(Node headA, Node headB) <
Node headC = null;
if (headA == null) <
return headB;
>
if (headB == null) <
return headA;
> if (headA.data headC = headA;
headC.next = mergeLists(headA.next, headB);
> else <
headC = headB;
headC.next = mergeLists(headA, headB.next);
>
return headC;
>

the last two loops should be while loop instead of if loops, consider an example where all the elements in l1 are smaller then all the elements in l2, in which case last if loop has to be a while and you also need to move the p2 pointer (p2 = p2.next)

The above solution doesn’t complete. Here is my solution: public static Node mergeTwoSortedLists(Node root1,Node root2) <
if(root1 == null)
return root2 == null?null:root2;
if(root2 == null)
return root1; Node returnNode, n1;
returnNode = n1 = root1.value < root2.value?root1:root2;
Node n2 = root1.value < root2.value?root2:root1; while(n1 != null && n2 != null)<
while(n1.child != null && n1.child.value n1 = n1.child;
Node oldChild = n1.child;
n1.child = n2;
n1 = n2;
n2 = oldChild;
>
return returnNode;
>

Recursive solution:
public static ListNode merge(ListNode n1, ListNode n2)
if (n1 == null) return n2;
if (n2 == null) return n1; ListNode node;
if (n1.val < n2.val)
node = n1;
node.next = merge(n1.next, n2);
>
else
node = n2;
node.next = merge(n1, n2.next);
>
return node;
>

I tried to do this with recursion and got stuck however I’m sure it’s possible. i also implemented this using two stacks which IMHO is a lot cleaner code than tracing loops. public static ListNode getStacked (ListNode l1, ListNode l2) < Stack s1= new Stack(); Stack s2= new Stack(); ListNode result=null,t=null; while(l1!=null) < s1.push(l1); l1=l1.next; >while(l2!=null) < s2.push(l2); l2=l2.next; >while(!s1.isEmpty() && !s2.isEmpty()) < if(s1.peek().val >s2.peek().val) t=s1.pop(); else t=s2.pop(); t.next=result; result=t; > if(s1.isEmpty()) < while(!s2.isEmpty()) < t=s2.pop(); t.next=result; result=t; >> else < while(!s1.isEmpty()) < t=s1.pop(); t.next=result; result=t; >> return result; >

After the while, considering that p = p1 or p = p2 is it necessary to do:
if(p1 != null)
p.next = p1;
if(p2 != null)
p.next = p2;

Источник

Merge Two Sorted Lists – Leetcode Solution

In this post, we are going to solve the 21. Merge Two Sorted Lists problem of Leetcode. This problem 21. Merge Two Sorted Lists is a Leetcode easy level problem. Let’s see the code, 21. Merge Two Sorted Lists – Leetcode Solution.

Problem

You are given the heads of two sorted linked lists list1 and list2 .

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1 :

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2 :

Input: list1 = [], list2 = [] Output: []

Example 3 :

Input: list1 = [], list2 = [0] Output: [0]

Constraints

Now, let’s see the code of 21. Merge Two Sorted Lists – Leetcode Solution.

Merge Two Sorted Lists – Leetcode Solution

21. Merge Two Sorted Lists – Solution in Java

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Java Programming Language.

/** * Definition for singly-linked list. * public class ListNode < * int val; * ListNode next; * ListNode() <>* ListNode(int val) < this.val = val; >* ListNode(int val, ListNode next) < this.val = val; this.next = next; >* > */ public class Solution < public ListNode mergeTwoLists(ListNode l1, ListNode l2) < ListNode head = new ListNode(0); ListNode handler = head; while(l1 != null && l2 != null) < if (l1.val else < handler.next = l2; l2 = l2.next; >handler = handler.next; > if (l1 != null) < handler.next = l1; >else if (l2 != null) < handler.next = l2; >return head.next; > >

Now let’s see the Recursive approach to solve the same problem in Java using Recursion.

/** * Definition for singly-linked list. * public class ListNode < * int val; * ListNode next; * ListNode() <>* ListNode(int val) < this.val = val; >* ListNode(int val, ListNode next) < this.val = val; this.next = next; >* > */ public class Solution < public ListNode mergeTwoLists(ListNode l1, ListNode l2) < if (l1 == null) return l2; if (l2 == null) return l1; ListNode handler; if(l1.val < l2.val) < handler = l1; handler.next = mergeTwoLists(l1.next, l2); >else < handler = l2; handler.next = mergeTwoLists(l1, l2.next); >return handler; > >

21. Merge Two Sorted Lists – Solution in C++

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in C++ Programming Language.

/** * Definition for singly-linked list. * struct ListNode < * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) <>* ListNode(int x) : val(x), next(nullptr) <> * ListNode(int x, ListNode *next) : val(x), next(next) <> * >; */ class Solution < public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) < ListNode* temp = new ListNode(-1); ListNode* head = temp; while(l1!=NULL and l2!=NULL)< if(l1->valval)< head->next = l1; l1 = l1->next; > else < head->next = l2; l2 = l2->next; > head=head->next; > if(l1!=NULL) < head->next = l1; > else head->next = l2; return temp->next; > >;

Now let’s see the Recursive approach to solve the same problem in C++ using Recursion.

/** * Definition for singly-linked list. * struct ListNode < * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) <>* ListNode(int x) : val(x), next(nullptr) <> * ListNode(int x, ListNode *next) : val(x), next(next) <> * >; */ class Solution < public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) < if(l1 == NULL) < return l2; >if(l2 == NULL) < return l1; >if(l1 -> val val) < l1 ->next = mergeTwoLists(l1 -> next, l2); return l1; > else < l2 ->next = mergeTwoLists(l1, l2 -> next); return l2; > > >;

21. Merge Two Sorted Lists – Solution in Python

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Python Programming Language.

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next def mergeTwoLists1(self, l1, l2): dummy = cur = ListNode(0) while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 or l2 return dummy.next

Now let’s see the Recursive approach to solve the same problem in Python using Recursion.

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next def mergeTwoLists2(self, l1, l2): if not l1 or not l2: return l1 or l2 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2

Note: This problem 21. Merge Two Sorted Lists is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Источник

Merge two sorted singly linked lists in java (example / recursive)

We have shown two sorted linked lists in Fig 1 and Fig 2. We would merge two linked list.

• Merged single linked list will contain nodes from both linked lists.
• Merged single linked list shall be sorted one.

Fig 2: Sorted Linked List 02

Algorithm or recursive method to merge two sorted linked lists in java

• Create merge method, taking head1 and head2 as method parameter
  • merge(Node head1, Node head2)
  • Create variable mergedList, which will point to head of merge linked list
  • return second linked list
  • so that, mergedList start point to second linked list
  • return first linked list
  • so that, mergedList start pointing first linked list
  • Check head1.data < head2.data
    • mergedList point to head1
    • now lets move ahead in linked list
      • head1.next and head2
      • mergeList points to head2
      • lets move ahead in linked list
        • head1 and head2.next

        Merged Linked list: We have shown the merged linked list in Fig 4, The merged linked list satisfy the criteria which we have defined earlier.

        

        Fig 3: Merged Linked list [Fig 1 and Fig 2]

        Program – Merge two sorted singly linked lists in java (recursive algorithm)

        1.) MergeLinkedLists Class:

        The MergeLinkedLists class has following methods

        • insert function will insert elements to single linked list
        • print function will print the single linked list
        • merge function will merge the two linked lists

        package org.learn.Question; import org.learn.List.Node; public class MergeLinkedLists < public static Node merge(Node head1, Node head2) < Node mergedList = null; if(head1 == null) < return head2; >if(head2 == null) < return head1; >if(head1.data < head2.data) < //point to smaller element mergedList = head1; mergedList.next = merge(head1.next, head2); >else < //head1 is large, so pass h //point to smaller element mergedList = head2; //head2 is already consider //now process next node of head2 mergedList.next = merge(head1, head2.next); >return mergedList; > public static void insert(Node head, int data) < while(head.next != null) head = head.next; head.next = new Node(data); >public static void print(Node head) < while(head != null) < System.out.printf("%d ",head.data); head = head.next; >System.out.println(""); > >

        2.) App Class:

        We are performing the following operation in App class

        • We are creating two linked lists in main method.
        • MergeLinkedLists.merge will merge two single linked lists
        • We are printing the linked list after merging the two linked list
          • MergeLinkedLists.print will print the single linked list

          package org.learn.Client; import org.learn.List.Node; import org.learn.Question.MergeLinkedLists; public class App < public static void main( String[] args ) < int[] data1 = ; Node head1 = new Node(data1[0]); for(int count = 1; count < data1.length; count++) MergeLinkedLists.insert(head1,data1[count]); System.out.printf("Linked list 1 is : "); MergeLinkedLists.print(head1); int[] data2 = ; Node head2 = new Node(data2[0]); for(int count = 1; count < data2.length; count++) MergeLinkedLists.insert(head2,data2[count]); System.out.printf("Linked list 2 is : "); MergeLinkedLists.print(head2); Node mergedList = MergeLinkedLists.merge(head1, head2); System.out.printf("Merged Linked list is : "); MergeLinkedLists.print(mergedList); >>

          3.) Node Class:

          package org.learn.List; public class Node < public int data; public Node next; public Node(int num) < this.data = num; this.next = null; >>

          Output – Merge two sorted singly linked lists in java (recursive algorithm)

          Linked list 1 is : 1 3 5 9 Linked list 2 is : 2 4 5 6 10 Merged Linked list is : 1 2 3 4 5 5 6 9 10

          Источник

          Читайте также:  Python list count method