fork download 
  1. // Solutions to exercises 3.2, 3.3 and 3.4
  2.  
  3. class Node {
  4.     int val;
  5.     Node next;
  6.     Node(int x) { val = x; }
  7.     public String toString() { return "Node: " + val; }
  8. }
  9.  
  10. class List {
  11.     Node head;
  12.     List(Node x) { head = x; }
  13.     List() { this(null); }
  14.  
  15.     public void append(Node x) {
  16. 	    if (head==null) {
  17. 	        head = x;
  18. 	    } else {
  19. 	        Node temp = head;
  20. 	        while (temp.next != null) {
  21. 		        temp = temp.next;
  22. 	        }
  23. 	    temp.next = x;
  24. 	    }
  25.     }
  26.  
  27.     public String toString() {
  28. 	String s = head + ", ";
  29.  
  30.         Node temp = head;
  31.         while (temp.next != null) {
  32.             temp = temp.next;
  33. 	    s += temp + ", ";
  34.         }
  35. 	return s;
  36.     }
  37.  
  38.     // Ex 3.3
  39.     public boolean checkCycle() {
  40.         Node tortoise = this.head;
  41.         Node hare     = this.head;
  42.         while(true) {
  43.             if(hare==null || hare.next==null) {
  44.                 System.out.println("Reached end of list, no cycles");
  45.                 return false;
  46.             }
  47.             hare     = hare.next.next;
  48.             tortoise = tortoise.next;
  49.  
  50.             if(tortoise == hare) {
  51.                 System.out.println("Cycle discovered");
  52.                 return true;
  53.             }
  54.         }
  55.     }
  56.  
  57.     // Ex 3.4
  58.     public Node kthBeforeLast(int k) {
  59.         Node temp1 = this.head;
  60.         Node temp2 = this.head;
  61.         int i = 0;
  62.  
  63.         // Set temp2 to the k+1th element in the list
  64.         while(i < k+1) {
  65.             if(temp2.next == null) {
  66.                 return temp1;
  67.             }
  68.             temp2 = temp2.next;
  69.             i++; 
  70.         }
  71.  
  72.         // Advance both one at the time.
  73.         // When temp2 reaches the end, temp1 is at the kth element from end.
  74.         while(temp2.next != null) {
  75.             temp1 = temp1.next;
  76.             temp2 = temp2.next;
  77.         }
  78.  
  79.         return temp1;
  80.     }
  81. }
  82.  
  83. class ListEx {
  84.  
  85.     // Ex 3.2
  86.     public static List listAdd(List one, List two) {
  87.         Node a = one.head; 
  88.         Node b = two.head;
  89.  
  90.         int va, vb;
  91.         int remainder = 0;
  92.  
  93.         List result = new List();
  94.  
  95.          while (!(a==null && b==null)) {
  96.  
  97.             va = (a==null) ? 0 : a.val; // If one list runs out of numbers,
  98.             vb = (b==null) ? 0 : b.val; // use 0 as the value for that position.
  99.  
  100.             int val = va + vb + remainder; // Add remainder from previous round
  101.  
  102.             if(val >= 10) {                // Set remainder for this round
  103.                 remainder = (val - remainder) / 10;
  104.                 val       = val - 10;
  105.             } else {
  106.                 remainder = 0;
  107.             }
  108.  
  109.             result.append(new Node(val));
  110.  
  111.             a = (a==null) ? null : a.next;
  112.             b = (b==null) ? null : b.next;
  113.          }
  114.  
  115.          if (remainder > 0) {
  116.              result.append(new Node(remainder));
  117.          }
  118.          return result;
  119.     }
  120.  
  121.  
  122.     public static void main(String [] args) {
  123.         Node one = new Node(1);
  124.         Node two = new Node(2);
  125.         Node three = new Node(3);
  126.         Node four = new Node(4);
  127.         Node five = new Node(5);
  128.  
  129.         List list = new List(one);
  130.         list.append(two);
  131.         list.append(three);
  132.         list.append(four);
  133.         list.append(five);
  134.         //Uncomment for cycle:
  135.         //five.next=three;
  136.  
  137.         System.out.println(list.checkCycle());
  138.  
  139.  
  140.         for (int i=0; i<4; i++) {
  141.             System.out.print(i + "th element before the last: ");
  142.             System.out.println(list.kthBeforeLast(i));
  143.         }
  144.  
  145.  
  146.         List test571 = new List();
  147.         test571.append(new Node(1));
  148.         test571.append(new Node(7));
  149.         test571.append(new Node(5));
  150.  
  151.         List test634 = new List();
  152.         test634.append(new Node(4));
  153.         test634.append(new Node(3));
  154.         test634.append(new Node(6));
  155.  
  156. 		System.out.println("\nAdd lists:");
  157. 		System.out.println(test571);
  158. 		System.out.println(test634);
  159.         System.out.println(listAdd(test571, test634));
  160.  
  161.         List test12345 = new List();
  162.         test12345.append(new Node(5));
  163.         test12345.append(new Node(4));
  164.         test12345.append(new Node(3));
  165.         test12345.append(new Node(2));
  166.         test12345.append(new Node(1));
  167.  
  168.         List test1 = new List(new Node(1));
  169.  
  170. 		System.out.println("\nAdd lists:");
  171. 		System.out.println(test12345);
  172. 		System.out.println(test1);
  173.         System.out.println(listAdd(test12345, test1));
  174.     }
  175. }
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin 
Standard input is empty
stdout 
Reached end of list, no cycles
false
0th element before the last: Node: 4
1th element before the last: Node: 3
2th element before the last: Node: 2
3th element before the last: Node: 1

Add lists:
Node: 1, Node: 7, Node: 5, 
Node: 4, Node: 3, Node: 6, 
Node: 5, Node: 0, Node: 2, Node: 1, 

Add lists:
Node: 5, Node: 4, Node: 3, Node: 2, Node: 1, 
Node: 1, 
Node: 6, Node: 4, Node: 3, Node: 2, Node: 1,
https://ideone.com/QRi7jQ
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!