We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Any recursive solution will take at least O(n+m) space due to O(n+m) recursive calls. Try to do it iteratively for a more space efficient solution.
NodeMergeLists(NodecurrA,NodecurrB){if(currA==null){returncurrB;}elseif(currB==null){returncurrA;}/* Find new head pointer */Nodehead=null;if(currA.data<currB.data){head=currA;currA=currA.next;}else{head=currB;currB=currB.next;}/* Build rest of list */Noden=head;while(currA!=null&&currB!=null){if(currA.data<currB.data){n.next=currA;currA=currA.next;}else{n.next=currB;currB=currB.next;}n=n.next;}/* Attach the remaining elements */if(currA==null){n.next=currB;}else{n.next=currA;}returnhead;}
Let's try an example
ListA:1->4->nullListB:2->nullCreated:null
Now the code labeled Find new head pointer will give us the following result:
ListA:4->nullListB:2->nullCreated:1->null
The code labeled Build rest of list will then give us:
ListA:4->nullListB:nullCreaetd:1->2
Finally, the code labeled Attach the remaining elements will complete our list:
Merge two sorted linked lists
You are viewing a single comment's thread. Return to all comments →
O(1) space complexity Java solution
From my HackerRank solutions.
Runtime: O(n +m)
Space Complexity: O(1)
Any recursive solution will take at least O(n+m) space due to O(n+m) recursive calls. Try to do it iteratively for a more space efficient solution.
Let's try an example
Now the code labeled Find new head pointer will give us the following result:
The code labeled Build rest of list will then give us:
Finally, the code labeled Attach the remaining elements will complete our list:
Let me know if you have any questions.