×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Java
Posted by: Shamir Yona
Added: Sep 23, 2015 3:26 PM
Views: 15
Tags: linkedlist
Linked lists tests
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package LinkedList;
  7.  
  8. /**
  9.  *
  10.  * @author shayzukerman
  11.  */
  12. public class MyLinkedList
  13. {
  14.     private Node head;
  15.     private Node tail;
  16.    
  17.     private int nodeCnt;
  18.  
  19.     public MyLinkedList()
  20.     {
  21.         this.head = this.tail = null;
  22.         this.nodeCnt = 0;
  23.     }
  24.    
  25.     public MyLinkedList(int[] inpArr)
  26.     {
  27.         this();
  28.         for (int val : inpArr)
  29.             this.addNode(val);
  30.     }
  31.    
  32.     /**
  33.      * Add new element to the List
  34.      * @param value - Node's value
  35.      */
  36.     public void addNode(int value)
  37.     {
  38.         Node newNode = new Node(value);
  39.        
  40.         if (head == null)
  41.             head = newNode;
  42.         else
  43.             tail.setNext(newNode);
  44.  
  45.         tail = newNode;
  46.         nodeCnt++;
  47.     }
  48.    
  49.     public void swapList()
  50.     {
  51.  
  52.         swapListRec(head, null);
  53. //        Node prev = null,
  54. //             curr,
  55. //             next;
  56. //        
  57. //        curr = tail = head;
  58. //        while (curr != null)
  59. //        {
  60. //            next = curr.getNext();
  61. //            curr.setNext(prev);
  62. //            prev = curr;
  63. //            curr = next;
  64. //        }
  65. //        head = prev;
  66.     }
  67.    
  68.     public void swapListRec(Node curr, Node prev)
  69.     {
  70.         Node next = curr.getNext();
  71.         if (next == null)
  72.         {
  73.             tail = head;
  74.             head = curr;
  75.         }
  76.         else
  77.             swapListRec(next, curr);
  78.         curr.setNext(prev);
  79.     }
  80.  
  81.     public void reorderList()
  82.     {
  83.         Node ptrHead1 = null, ptrTai11 = null,
  84.              ptrHead2 = null, ptrTail2 = null;
  85.              Node curr1, curr2;
  86.         Node ptr = head;
  87.         curr2 = null;
  88.  
  89.         if (head == null)
  90.             return;
  91.        
  92.         boolean add2ptr1 = true;
  93.         while (ptr != null)
  94.         {
  95.             Node next = ptr.getNext();
  96.             if (add2ptr1)
  97.             {
  98.                 if (ptrHead1 == null)
  99.                     ptrHead1 = ptr;
  100.                 else
  101.                     ptrTai11.setNext(ptr);
  102.              
  103.                 ptrTai11 = ptr;
  104.                 // Since we don't know if we reach here at the end of the
  105.                 // scan, always assign null at the end of the list:
  106.                 ptrTai11.setNext(null);
  107.                 add2ptr1 = false;
  108.             }
  109.             else
  110.             {
  111.                 if (ptrTail2 == null)
  112.                     ptrTail2 = ptr;
  113.                
  114.                 ptr.setNext(curr2);
  115.                 // Since we don't know if we reach here at the end of the
  116.                 // scan, always assign the current node to head:
  117.                 ptrHead2 = ptr;
  118.                 curr2 = ptr;
  119.                 add2ptr1 = true;
  120.             }
  121.                
  122.             ptr = next;
  123.         }
  124.        
  125.         System.out.println("List1: " + linkedList2Str(ptrHead1));
  126.         System.out.println("List2: " + linkedList2Str(ptrHead2));
  127.        
  128.         Node newHead = null;
  129.         Node newTail = null;
  130.         curr1 = ptrHead1;
  131.         curr2 = ptrHead2;
  132.        
  133.         add2ptr1 = true;
  134.         while (curr1 != null || curr2 != null)
  135.         {
  136.             ptr = (add2ptr1) ? curr1 : curr2;
  137.             if (ptr != null)
  138.             {  
  139.                 if (newHead == null)
  140.                     newHead = ptr;
  141.                 else
  142.                    newTail.setNext(ptr);
  143.                 newTail = ptr;
  144.             }
  145.             if (add2ptr1)
  146.             {
  147.                 curr1 = curr1.getNext();
  148.                 if (curr2 != null)
  149.                     add2ptr1 = false;
  150.             }
  151.             else
  152.             {
  153.                 curr2 = curr2.getNext();
  154.                 if (curr1 != null)
  155.                     add2ptr1 = true;
  156.             }
  157.         }
  158.         head = newHead;
  159.         tail = newTail;
  160.     }
  161.    
  162.    
  163.     @Override
  164.     public String toString()
  165.     {
  166.         return (linkedList2Str(this.head));
  167.     }
  168.    
  169.     public String linkedList2Str(Node head)
  170.     {
  171.         if (head == null)
  172.            return ("{enpty}");
  173.        
  174.         StringBuilder retStb = new StringBuilder();
  175.        
  176.         for (Node ptr = head; ptr != null; ptr = ptr.getNext())
  177.             retStb.append(ptr);
  178.        
  179.         return("{ " + retStb.toString() + " }");
  180.     }
  181.    
  182.    
  183.     public static void main(String[] args)
  184.     {
  185.         int[] inpArr = {1, 2, 3, 4};
  186.         //int[] inpArr = {1, 2, 3};
  187.         MyLinkedList myList = new MyLinkedList(inpArr);
  188.         System.out.println("My List: " + myList);
  189.        
  190.         myList.reorderList();
  191.         System.out.println("My List: " + myList);
  192.         myList.swapList();
  193.         System.out.println("My List: " + myList);
  194. //        myList.addNode(1);
  195. //        System.out.println("My List: " + myList);
  196. //        myList.swapList();
  197. //        System.out.println("My List: " + myList);
  198.        
  199.     }
  200.    
  201. }
  202.