contestada

you are given two sorted circular linked lists of integers. the difference of the first list with respect to the second is the set of all items that are in the first list but not in the second. implement a non recursive method to compute the difference and return it in a new circular linked list

Respuesta :

abdullahfarooqi

Answer:

public class CircularLinkedList {

 

  public Node n1;

 

  public static void main(String[] args) {

      CircularLinkedList c = new CircularLinkedList();

      c.callMethod();

  }

 

  public void callMethod() {

      Node n1 = new Node(3,null);

      n1.next = n1;

      Node n2 = new Node(2,null);

      n2.next = n2;

      //as first root element is already created

      int[] n1Data = {9,12,15,19,21,23};

      int[] n2Data = {3,6,12,19};

      addMultipleData(n1,n1Data);

      addMultipleData(n2,n2Data);

      //printNode(n1);

      printNode(difference(n1,n2));

  }

 

  public Node addData(Node root,Node n,int data) {

      Node temp = new Node(data,n.next);

      n.next = temp;

      return n.next;

  }

 

  public Node addMultipleData(Node n,int... arr) {

      Node temp = null;

      for(int i = 0;i<arr.length;i++) {

          temp = new Node(arr[i],n.next);

          n.next = temp;

          n = temp;

      }

      return temp;

  }

 

  //this is a method you are looking for

  public Node difference(Node rearL1,Node rearL2) {

      //return value

      Node differenceNode = null;

      Node i,j,k,l;

      i=j = rearL1;

      k=l=rearL2;

      Node differenceNodeRoot = differenceNode;

     

      boolean firstListCheckNeeded = false;

      int c1 = 0,c2 = 0;

      while(true) {

          while(k.data<i.data) {

              if(k==l && c2 != 0) {

                  firstListCheckNeeded = true;

                  break;

              }

              k = k.next;

              c2++;

          }

          //if the iner while loop breaks that means the second list has ended so no need to go further

          if(firstListCheckNeeded)break;

         

          if(k.data == i.data) {

              i = i.next;

              c1++;

              continue;

          }else {

              Node temp = new Node(i.data,differenceNodeRoot);

              if(differenceNode == null) {

                  differenceNode = temp;

                  temp.next = temp;

                  differenceNodeRoot = temp;

              }else {

              differenceNode.next = temp;

              differenceNode = differenceNode.next;

              }

              i = i.next;

              c1++;

          }

          //check to see if we have reached the root

          if(i==j && c1 != 0) {

              //first list iteration complete

              break;

          }

          else if(k==l && c2 != 0) {

              firstListCheckNeeded = true;

              break;

          }

          //break;

      }

      if(firstListCheckNeeded) {

          while(i != j) {

              Node temp = new Node(i.data,differenceNodeRoot);

              if(differenceNode == null) {

                  differenceNode = temp;

                  temp.next = temp;

              }else {

              differenceNode.next = temp;

              differenceNode = differenceNode.next;

              }

              i = i.next;

          }

      }

      return differenceNode.next;

  }

 

  public void printNode(Node n) {

      if(n == null) {

          System.out.println("Node is Empty");

      }

      Node i,j;

      i = j = n;

      System.out.println("Values");

      System.out.println(i.data);

      i = i.next;

      while(i!=j) {

          System.out.println(i.data);

          i = i.next;

      }

     

  }

  class Node {

      public int data;

      public Node next;

      public Node(int data,Node next) {

          this.data = data;

          this.next = next;

      }

  }

}

Explanation:

Otras preguntas