API tools faq
paste
mjain

Linked List

mjain
Jun 11th, 2019
80
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 17.68 KB | None | 0 0
raw download clone embed print report
  1. package testrun;
  2.  
  3. public class LinkedList {
  4.  
  5.     public static void main(String[] args) {
  6.         Node start = new Node(1);
  7.         start.next = new Node(2);
  8.         start.next.next = new Node(3);
  9.         start.next.next.next = new Node(4);
  10.         start.next.next.next.next = new Node(5);
  11.  
  12.         // 1's random points to 3
  13.         start.random = start.next.next;
  14.  
  15.         // 2's random points to 1
  16.         start.next.random = start;
  17.  
  18.         // 3's and 4's random points to 5
  19.         start.next.next.random = start.next.next.next.next;
  20.         start.next.next.next.random = start.next.next.next.next;
  21.  
  22.         // 5's random points to 2
  23.         start.next.next.next.next.random = start.next;
  24.  
  25.         System.out.println("Original list : ");
  26.  
  27.         printList(start);
  28.         cloneLinkedListWithNextAndRandomPointer(start);
  29.         // Node head2 = new Node(0);
  30.         // head2.next = new Node(3);
  31.         // head2.next.next = new Node(12);
  32.         // head2.next.next.next = new Node(32);
  33.         // head2.next.next.next.next = new Node(90);
  34.         // head2.next.next.next.next.next = new Node(100);
  35.         // head2.next.next.next.next.next.next = new Node(120);
  36.         // head2.next.next.next.next.next.next.next = new Node(130);
  37.         // printMaxPathLL(head, head2);
  38.         // addTwoLL(head, head2);
  39.         // head.next.next.next.next = new Node(5);
  40.         // head.next.next.next.next.next = new Node(6);
  41.         // head.next.next.next.next.next = new Node(6);
  42.         // printList(head);
  43.         // KthElementFromLast(head, 2);
  44.         // head = rearrangeAtOddEven(head);
  45.         // printList(head);
  46.         // reverseLLIterative(head);
  47.         // pairWiseSwap(head);
  48.         // sunOfTwoLinkedList(head, head2);
  49.         // boolean isPalin = isPalindrom(head);
  50.         // System.out.print("is Palindrom: " + isPalin);
  51.     }
  52.  
  53.     public static void cloneLinkedListWithNextAndRandomPointer(Node original) {
  54.         if (original == null) {
  55.             return;
  56.         }
  57.         Node headCopy = original;
  58.         while (headCopy != null) {
  59.             Node curCopy = new Node(headCopy.data);
  60.             Node temp = headCopy.next;
  61.             headCopy.next = curCopy;
  62.             curCopy.next = temp;
  63.             headCopy = temp;
  64.         }
  65.         // printList(original);
  66.         headCopy = original;
  67.  
  68.         while (headCopy != null) {
  69.             if (headCopy.next != null) {
  70.                 headCopy.next.random = headCopy.random != null ? headCopy.random.next : headCopy.random;
  71.             }
  72.  
  73.             headCopy = headCopy.next.next;
  74.         }
  75.         headCopy = original;
  76.         Node copyHead = original.next;
  77.         Node copy = original.next;
  78.         while (headCopy != null && headCopy.next != null && copy != null && copy.next != null) {
  79.             headCopy = headCopy.next.next;
  80.             copy = copy.next.next;
  81.         }
  82.  
  83.         printList(original);
  84.         printList(copyHead);
  85.  
  86.     }
  87.  
  88.     public static void printMaxPathLL(Node head1, Node head2) {
  89.         if (head1 == null && head1 == null) {
  90.             return;
  91.         }
  92.         printList(head1);
  93.         printList(head2);
  94.         Node prevA = head1, prevB = head2, a = head1, b = head2;
  95.         Node result = null;
  96.         while (a != null || b != null) {
  97.             int sumA = 0;
  98.             int sumB = 0;
  99.             while (a != null && b != null && a.data != b.data) {
  100.                 if (a.data < b.data) {
  101.                     sumA += a.data;
  102.                     a = a.next;
  103.                 } else {
  104.                     sumB += b.data;
  105.                     b = b.next;
  106.                 }
  107.             }
  108.  
  109.             if (a == null) {
  110.                 System.out.print("First");
  111.                 while (b != null) {
  112.                     sumA += b.data;
  113.                     b = b.next;
  114.                 }
  115.             }
  116.             if (b == null) {
  117.                 while (a != null) {
  118.                     sumB += a.data;
  119.                     a = a.next;
  120.                 }
  121.             }
  122.  
  123.             System.out.println("sumA: " + sumA);
  124.             System.out.println("sumB: " + sumB);
  125.             System.out.println("prevB: " + prevB.data);
  126.             System.out.println("prevA: " + prevA.data);
  127.             if (prevA == head1 && prevB == head2) {
  128.                 result = (sumA > sumB) ? prevA : prevB;
  129.             } else {
  130.                 if (sumA > sumB) {
  131.                     prevB.next = prevA.next;
  132.                 } else {
  133.                     prevA.next = prevB.next;
  134.                 }
  135.             }
  136.             prevA = a;
  137.             prevB = b;
  138.             if (a != null) {
  139.                 a = a.next;
  140.             }
  141.  
  142.             if (b != null) {
  143.                 b = b.next;
  144.             }
  145.             System.out.print("Result list");
  146.             printList(result);
  147.         }
  148.         // printList(result);
  149.     }
  150.  
  151.     static Node thirdLL = null;
  152.     static int  s_carry = 0;
  153.  
  154.     public static int addSameSize(Node a, Node b) {
  155.         if (a == null) {
  156.             return 0;
  157.         }
  158.         int carry = addSameSize(a.next, b.next);
  159.         int sum = a.data + b.data + carry;
  160.         carry = sum / 10;
  161.         sum = sum % 10;
  162.         if (thirdLL == null) {
  163.             thirdLL = new Node(sum);
  164.         } else {
  165.             Node temp = new Node(sum);
  166.             temp.next = thirdLL;
  167.             thirdLL = temp;
  168.         }
  169.         return carry;
  170.     }
  171.  
  172.     public static void addTwoLL(Node a, Node b) {
  173.         if (a == null && b == null) {
  174.             return;
  175.         }
  176.         int size1 = lengthOfLL(a);
  177.         int size2 = lengthOfLL(b);
  178.         printList(a);
  179.         printList(b);
  180.         if (size1 == size2) {
  181.             addSameSize(a, b);
  182.         } else {
  183.             int diff = Math.abs(size1 - size2);
  184.             Node biggerListHead = a;
  185.             Node temp = a;
  186.             Node other = b;
  187.             if (size2 > size1) {
  188.                 biggerListHead = b;
  189.                 temp = b;
  190.                 other = a;
  191.             }
  192.             int count = 0;
  193.             while (count < diff) {
  194.                 temp = temp.next;
  195.                 count++;
  196.             }
  197.             s_carry = addSameSize(temp, other);
  198.             fillbiggerList(biggerListHead, diff, 0);
  199.         }
  200.         printList(thirdLL);
  201.  
  202.     }
  203.  
  204.     public static void fillbiggerList(Node a, int diff, int cutCount) {
  205.         if (a == null || cutCount >= diff) {
  206.             return;
  207.         }
  208.         fillbiggerList(a.next, diff, cutCount + 1);
  209.         int sum = a.data + s_carry;
  210.         s_carry = sum / 10;
  211.         sum = sum % 10;
  212.         if (thirdLL == null) {
  213.             thirdLL = new Node(sum);
  214.         } else {
  215.             Node temp = new Node(sum);
  216.             temp.next = thirdLL;
  217.             thirdLL = temp;
  218.         }
  219.     }
  220.  
  221.     public static void sunOfTwoLinkedList(Node headOne, Node headTwo) {
  222.         // edge cases
  223.         if (headOne == null && headTwo == null) {
  224.             return;
  225.         }
  226.         if (headOne == null && headTwo != null) {
  227.             printList(headTwo);
  228.             return;
  229.         }
  230.         if (headOne != null && headTwo == null) {
  231.             printList(headOne);
  232.             return;
  233.         }
  234.         printList(headOne);
  235.         printList(headTwo);
  236.         headOne = reverseLLIterative(headOne);
  237.         headTwo = reverseLLIterative(headTwo);
  238.         Node resultHead = null;
  239.         int carry = 0;
  240.         while (headOne != null && headTwo != null) {
  241.             int sum = headOne.data + headTwo.data + carry;
  242.             if (resultHead == null) {
  243.                 resultHead = new Node(sum % 10);
  244.             } else {
  245.                 Node temp = new Node(sum % 10);
  246.                 temp.next = resultHead;
  247.                 resultHead = temp;
  248.             }
  249.             carry = sum / 10;
  250.             headOne = headOne.next;
  251.             headTwo = headTwo.next;
  252.         }
  253.         while (headOne != null) {
  254.             int sum = headOne.data + carry;
  255.             Node temp = new Node(sum % 10);
  256.             temp.next = resultHead;
  257.             resultHead = temp;
  258.             headOne = headOne.next;
  259.             carry = sum / 10;
  260.         }
  261.         while (headTwo != null) {
  262.             int sum = headTwo.data + carry;
  263.             Node temp = new Node(sum % 10);
  264.             temp.next = resultHead;
  265.             resultHead = temp;
  266.             headTwo = headTwo.next;
  267.             carry = sum / 10;
  268.         }
  269.         if (carry > 0) {
  270.             Node temp = new Node(carry);
  271.             temp.next = resultHead;
  272.             resultHead = temp;
  273.         }
  274.         System.out.println("Sum Linked List:");
  275.         printList(resultHead);
  276.     }
  277.  
  278.     public static void pairWiseSwap(Node head) {
  279.         System.out.println("Pair Wise swap: ");
  280.         if (head == null) {
  281.             return;
  282.         }
  283.         Node curNode = head;
  284.         while (curNode != null && curNode.next != null) {
  285.             int data = curNode.data;
  286.             curNode.data = curNode.next.data;
  287.             curNode.next.data = data;
  288.             curNode = curNode.next.next;
  289.         }
  290.         printList(head);
  291.     }
  292.  
  293.  public static Node reverseLLRecusrive(Node head) {
  294.         if (head == null) {
  295.             return null;
  296.         }
  297.         if (head.next == null) {
  298.             return head;
  299.         }
  300.         Node newHead = reverseLLRecusrive(head.next);
  301.         head.next.next = head;
  302.         head.next = null;
  303.         return newHead;
  304.     }
  305.    
  306.     static Node reverseLLForGivenK(Node head, int k) {
  307.         Node current = head;
  308.         Node next = null;
  309.         Node prev = null;
  310.         int count = 0;
  311.         while (count < k && current != null) {
  312.             next = current.next;
  313.             current.next = prev;
  314.             prev = current;
  315.             current = next;
  316.             count++;
  317.         }
  318.  
  319.         if (next != null) {
  320.             head.next = reverseLLForGivenK(next, k);
  321.         }
  322.         return prev;
  323.     }
  324.  
  325.     public static void rotateAtKthPosition(Node head, int k) {
  326.         if (head == null) {
  327.             return;
  328.         }
  329.         int count = 1;
  330.         Node curNode = head;
  331.         while (count < k && curNode != null) {
  332.             curNode = curNode.next;
  333.             count++;
  334.         }
  335.  
  336.         if (curNode == null) {
  337.             return;
  338.         }
  339.  
  340.         Node kthnode = curNode;
  341.  
  342.         while (curNode.next != null) {
  343.             curNode = curNode.next;
  344.         }
  345.  
  346.         curNode.next = head;
  347.         head = kthnode.next;
  348.         kthnode.next = null;
  349.         printList(head);
  350.     }
  351.  
  352.     public static boolean isPalindrom(Node head) {
  353.         Node middleNode = printMiddleOfLL(head);
  354.         if (middleNode != null) {
  355.             middleNode = reverseLLIterative(middleNode);
  356.             Node firstHalfHead = head;
  357.             Node secondHalfNode = middleNode;
  358.             while (firstHalfHead != null && secondHalfNode != null) {
  359.                 if (firstHalfHead.data != secondHalfNode.data) {
  360.                     return false;
  361.                 }
  362.                 firstHalfHead = firstHalfHead.next;
  363.                 secondHalfNode = secondHalfNode.next;
  364.             }
  365.         }
  366.         return true;
  367.     }
  368.  
  369.     public static Node reverseLLIterative(Node head) {
  370.         Node prev = null;
  371.         Node next = null;
  372.         Node cur = head;
  373.         while (cur != null) {
  374.             next = cur.next;
  375.             cur.next = prev;
  376.             prev = cur;
  377.             cur = next;
  378.         }
  379.         head = prev;
  380.         return head;
  381.     }
  382.  
  383.     public static int lengthOfLL(Node head) {
  384.         Node temp = head;
  385.         int size = 0;
  386.         while (temp != null) {
  387.             size++;
  388.             temp = temp.next;
  389.         }
  390.         System.out.println("Size of LL: " + size);
  391.         return size;
  392.     }
  393.  
  394.     public static void KthElementFromLast(Node head, int k) {
  395.         Node temp = head;
  396.         int length = lengthOfLL(temp);
  397.         if (length < k) {
  398.             return;
  399.         }
  400.         temp = head;
  401.         int indexFrombegining = length - k + 1;
  402.         for (int i = 1; i < indexFrombegining; i++) {
  403.             temp = temp.next;
  404.         }
  405.         System.out.print("Element from " + k + "th index from end: " + temp.data);
  406.  
  407.     }
  408.  
  409.     public static Node printMiddleOfLL(Node head) {
  410.         if (head == null) {
  411.             return null;
  412.         }
  413.         Node temp = head;
  414.         Node fastNode = temp;
  415.         Node slowNode = temp;
  416.         while (fastNode != null && fastNode.next != null) {
  417.             fastNode = fastNode.next.next;
  418.             slowNode = slowNode.next;
  419.         }
  420.         System.out.println("Mid of LL: " + slowNode.data);
  421.         return slowNode;
  422.     }
  423.  
  424.     public static Node splitListIntoTwoHalf(Node head) {
  425.         if (head == null) {
  426.             return null;
  427.         }
  428.         Node temp = head;
  429.         Node fastNode = temp;
  430.         Node slowNode = temp;
  431.         while (fastNode != null && fastNode.next != null) {
  432.             fastNode = fastNode.next.next;
  433.             slowNode = slowNode.next;
  434.         }
  435.         fastNode.next = null;
  436.         System.out.println("Mid of LL: " + slowNode.data);
  437.         return slowNode;
  438.     }
  439.  
  440.     public static Node rearrangeAtOddEven(Node head) {
  441.         if (head == null) {
  442.             return null;
  443.         }
  444.         Node oddNode = head, evenNode = head.next, preEvenNode = evenNode;
  445.         while (true) {
  446.             // break condition ,if LL reaches at end or even or next to even are
  447.             // null,connect odd position list to first even node
  448.             if (oddNode == null || evenNode == null || evenNode.next == null) {
  449.                 oddNode.next = preEvenNode;
  450.                 break;
  451.             }
  452.             // rearrange pointers for example connect first to thrid
  453.             oddNode.next = evenNode.next;
  454.             // increment odd node by skipping one
  455.             oddNode = evenNode.next;
  456.             // if reaches at end,connect first even node to odd list
  457.             if (oddNode.next == null) {
  458.                 evenNode.next = null;
  459.                 oddNode.next = preEvenNode;
  460.             }
  461.             // rearrange evenNode pointers
  462.             evenNode.next = oddNode.next;
  463.             // increment even node by skipping one
  464.             evenNode = oddNode.next;
  465.         }
  466.  
  467.         return head;
  468.     }
  469.  
  470.     public boolean detectCycle(Node head) {
  471.         if (head == null || head.next == null) {
  472.             return false;
  473.         }
  474.         Node fast = head;
  475.         Node slow = head;
  476.         while (slow != null && fast != null && fast.next != null) {
  477.             fast = fast.next.next;
  478.             slow = slow.next;
  479.             if (fast != null && slow != null) {
  480.                 if (fast == slow) {
  481.                     return true;
  482.                 }
  483.             }
  484.         }
  485.         return false;
  486.     }
  487.  
  488.     public static Node mergePointINtwoLL(Node head1, Node head2) {
  489.         if (head1 == null && head2 == null) {
  490.             return null;
  491.         }
  492.         int lengthOfFirstLL = lengthOfLL(head1);
  493.         int lengthOfSecondLL = lengthOfLL(head2);
  494.  
  495.         int diffrence = Math.abs(lengthOfFirstLL - lengthOfSecondLL);
  496.         Node firstNode = null, secondNode = null;
  497.         if (lengthOfFirstLL > lengthOfSecondLL) {
  498.             firstNode = head1;
  499.             secondNode = head2;
  500.         } else {
  501.             firstNode = head2;
  502.             secondNode = head1;
  503.         }
  504.  
  505.         int count = 0;
  506.         while (count < diffrence) {
  507.             firstNode = firstNode.next;
  508.         }
  509.         while (firstNode != null && secondNode != null) {
  510.             if (firstNode == secondNode) {
  511.                 return firstNode;
  512.             }
  513.             firstNode = firstNode.next;
  514.             secondNode = secondNode.next;
  515.         }
  516.  
  517.         return null;
  518.     }
  519.  
  520.     public static void printList(Node head) {
  521.         Node temp = head;
  522.         while (temp != null) {
  523.             System.out.print(temp.data + "->");
  524.             temp = temp.next;
  525.         }
  526.         System.out.println("NULL");
  527.     }
  528.  
  529.     public static Node mergeTwoSortedLL(Node a, Node b) {
  530.         Node resultLL = null;
  531.         if (a == null && b == null) {
  532.             return null;
  533.         }
  534.         if (a == null) {
  535.             return b;
  536.         }
  537.         if (b == null) {
  538.             return a;
  539.         }
  540.         if (a.data > b.data) {
  541.             resultLL = b;
  542.             resultLL.next = mergeTwoSortedLL(a, b.next);
  543.         } else {
  544.             resultLL = a;
  545.             resultLL.next = mergeTwoSortedLL(a.next, b);
  546.         }
  547.  
  548.         return resultLL;
  549.     }
  550.  
  551.     public static Node mergeSort(Node head) {
  552.         if (head == null || head.next == null) {
  553.             return head;
  554.         }
  555.         Node mid = printMiddleOfLL(head);
  556.         Node midNext = mid.next;
  557.         // set null to next to mid to split the list
  558.         mid.next = null;
  559.         Node leftList = mergeSort(head);
  560.         Node rightList = mergeSort(midNext);
  561.         return mergeTwoSortedLL(leftList, rightList);
  562.     }
  563.  
  564.     static class Node {
  565.         int  data;
  566.         Node next;
  567.         Node random;
  568.  
  569.         public Node() {
  570.             super();
  571.         }
  572.  
  573.         public Node(int data) {
  574.             super();
  575.             this.data = data;
  576.             this.next = null;
  577.         }
  578.  
  579.         public Node(int data, Node next) {
  580.             super();
  581.             this.data = data;
  582.             this.next = next;
  583.         }
  584.  
  585.         public int getData() {
  586.             return data;
  587.         }
  588.  
  589.         public void setData(int data) {
  590.             this.data = data;
  591.         }
  592.  
  593.         public Node getNext() {
  594.             return next;
  595.         }
  596.  
  597.         public void setNext(Node next) {
  598.             this.next = next;
  599.         }
  600.  
  601.         public void setRandom(Node r) {
  602.             this.random = r;
  603.         }
  604.  
  605.     }
  606. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!