Advertisement
satishfrontenddev4

Untitled

Jan 5th, 2024
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
  3.  
  4. Return a deep copy of the list i.e. the head of the copied linked list.
  5.  
  6. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
  7.  
  8. For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
  9.  
  10. The original list should be restored if modified.
  11.  
  12. Input format:
  13. Next line contains X space separated integers, elements of the linked list.
  14.  
  15. Next line contains X space separated integers, random pointers of each node in the linked list.
  16.  
  17. Output format
  18. Return a deep copy of the list i.e. the head of the copied linked list.
  19.  
  20. Sample Input 1
  21. 10 20
  22.  
  23. 2 2
  24.  
  25. Sample Output 1
  26. 10 20
  27.  
  28. 20 20
  29.  
  30. Explanation 1
  31. ========================
  32.  
  33. View of the Linked list
  34.  
  35. ========================
  36.  
  37. {10.next} -> {20}
  38.  
  39. and
  40.  
  41. {20.next} -> {null}
  42.  
  43. {10.random} -> {20}
  44.  
  45. and
  46.  
  47. {20.random} -> {20}
  48.  
  49. Constraints
  50. 3 <= K <= N <= 105
  51.  
  52. |A[i]| <= 109
  53. */
  54.  
  55. /*
  56. class ListNode{
  57.     constructor(val){
  58.         this.val = val;
  59.         this.next = null;
  60.     }
  61. */
  62.  
  63. /**
  64.  * @param {ListNode} head1
  65.  * @param {ListNode} head2
  66.  * @return {ListNode}
  67.  */
  68. function sumLists2(head1, head2) {
  69.       let str1='',str2='';
  70.       let pointer1=head1, pointer2=head2;
  71.       let carry=0;
  72.       let length1=0,length2=0;
  73.       let result='';
  74.       if(pointer1==null)
  75.             return pointer2;
  76.       if(pointer2==null)
  77.             return pointer1
  78.       while(pointer1!=null){
  79.             str1=str1+pointer1.val.toString();
  80.             length1++;
  81.             pointer1=pointer1.next;
  82.       }
  83.  
  84.       while(pointer2!=null){
  85.             str2=str2+pointer2.val.toString();
  86.             length2++;
  87.             pointer2=pointer2.next;
  88.       }
  89.  
  90.       // console.log(str1);
  91.       let i=length1-1;
  92.       let j=length2-1;
  93.       while(i>=0&&j>=0){
  94.             let currentVal=parseInt(str1[i])+parseInt(str2[j])+carry;
  95.             carry=Math.floor(currentVal/10);
  96.             currentVal=Math.floor(currentVal%10).toString();
  97.             result=currentVal.toString()+result;
  98.             i--;
  99.             j--;
  100.       }
  101.  
  102.       while(i>=0){
  103.             // means str1 is remaining
  104.             let currentVal=parseInt(str1[i])+carry;
  105.             carry=Math.floor(currentVal/10);
  106.             currentVal=Math.floor(currentVal%10).toString();
  107.             result=currentVal.toString()+result;
  108.             i--;
  109.       }
  110.  
  111.        while(j>=0){
  112.             // means str1 js remajnjng
  113.             let currentVal=parseInt(str2[j])+carry;
  114.             carry=Math.floor(currentVal/10);
  115.             currentVal=Math.floor(currentVal%10).toString();
  116.             result=currentVal.toString()+result;
  117.             j--;
  118.       }
  119.  
  120.       if(carry>0)
  121.            result=carry.toString()+result;
  122.       // console.log(result);
  123.  
  124.       // nopw simply convert resultant string into linkedList
  125.  
  126.       i=0;
  127.       let currentPointer=null;
  128.       let head=null;
  129.       while(i<result.length){
  130.             let newNode= new ListNode(parseInt(result[i]));
  131.             if(currentPointer==null){
  132.                   currentPointer=newNode;
  133.                   head=currentPointer;
  134.             }
  135.             else{
  136.                   currentPointer.next=newNode;
  137.                   currentPointer=currentPointer.next;
  138.             }
  139.             i++;
  140.       }
  141.  
  142.       return head;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement