首页 > 代码库 > 单链表反转(Singly Linked Lists in Java)

单链表反转(Singly Linked Lists in Java)

2024-07-08 21:35:41   226人阅读

 

单链表反转(Singly Linked Lists in Java)

博客分类：
     
  • 数据结构及算法
 
Java代码  收藏代码
  1. package dsa.linkedlist;  
  2.   
  3. public class Node<E>{  
  4.  E data;  
  5.  Node<E> next;  
  6. }  
 
Java代码  收藏代码
  1. package dsa.linkedlist;  
  2.   
  3. public class ReverseLinkedListRecursively {  
  4.   
  5.     public static void main(String args[]) {  
  6.         ReverseLinkedListRecursively reverser = new ReverseLinkedListRecursively();  
  7.         SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);  
  8.         System.out.println("Original List : " + originalList.toString());  
  9.         originalList.start = reverser.reverse(originalList.start);  
  10.         System.out.println("Reversed List : " + originalList.toString());  
  11.     }  
  12.   
  13.     public Node<Integer> reverse(Node<Integer> list) {  
  14.         if (list == null || list.next == null)  
  15.             return list;  
  16.         Node<Integer> nextItem = list.next;  
  17.         list.next = null;  
  18.         Node<Integer> reverseRest = reverse(nextItem);  
  19.         nextItem.next = list;  
  20.         return reverseRest;  
  21.     }  
  22.   
  23.     private SinglyLinkedList<Integer> getLabRatList(int count) {  
  24.         SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();  
  25.         for (int i = 0; i < count; i++) {  
  26.             sampleList.add(i);  
  27.         }  
  28.         return sampleList;  
  29.     }  
  30. }  
  31. /* 
  32.  * SAMPLE OUTPUT Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Reversed List : 9, 
  33.  * 8, 7, 6, 5, 4, 3, 2, 1, 0 
  34.  */  
 
Java代码  收藏代码
  1. package dsa.linkedlist;  
  2.   
  3. /** 
  4.  * This is a singly linked list with no prev pointer. 
  5.  * @author Braga 
  6.  * @param <E> 
  7.  */  
  8. public class SinglyLinkedList<E> {  
  9.    
  10.  Node<E> start;  
  11.  int size;  
  12.    
  13.  public SinglyLinkedList(){  
  14.   start = null;  
  15.   size = 0;  
  16.  }  
  17.    
  18.  //insertAtLast  
  19.  public void add(E data){  
  20.   insertAtLast(data);  
  21.  }  
  22.    
  23.  public void insertAtLast(E data){  
  24.   if(size==0){  
  25.    start = new Node<E>();  
  26.    start.next = null;  
  27.    start.data = data;  
  28.   }else{  
  29.    Node<E> currentNode = getNodeAt(size-1);  
  30.    Node<E> newNode = new Node<E>();  
  31.    newNode.data = data;  
  32.    newNode.next = null;  
  33.    currentNode.next = newNode;  
  34.   }  
  35.   size++;  
  36.  }  
  37.    
  38.  public void insertAtFirst(E data){  
  39.   if(size==0){  
  40.    start = new Node<E>();  
  41.    start.next = null;  
  42.    start.data = data;  
  43.   }else{  
  44.    Node<E> newNode = new Node<E>();  
  45.    newNode.data = data;  
  46.    newNode.next = start;  
  47.    start = newNode;  
  48.   }  
  49.   size++;  
  50.  }  
  51.    
  52.  public Node<E> getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException{  
  53.   if(nodePos>=size || nodePos<0){  
  54.    throw new ArrayIndexOutOfBoundsException();  
  55.   }  
  56.   Node<E> temp = start;//Move pointer to front  
  57.   int counter = 0;  
  58.   for(;counter<nodePos;counter++){  
  59.    temp = temp.next;  
  60.   }  
  61.   return temp;  
  62.  }  
  63.    
  64.  public void insertAt(int position, E data){  
  65.   if(position == 0){  
  66.    insertAtFirst(data);  
  67.   }else if(position==size-1){  
  68.    insertAtLast(data);  
  69.   }else{  
  70.    Node<E> tempNode = getNodeAt(position-1);  
  71.    Node<E> newNode = new Node<E>();  
  72.    newNode.data = data;  
  73.    newNode.next = tempNode.next;  
  74.    tempNode.next = newNode;  
  75.    size++;  
  76.   }  
  77.  }  
  78.    
  79.  public Node<E> getFirst(){  
  80.   return getNodeAt(0);  
  81.  }  
  82.    
  83.  public Node<E> getLast(){  
  84.   return getNodeAt(size-1);  
  85.  }  
  86.    
  87.  public E removeAtFirst(){  
  88.   if(size==0){  
  89.    throw new ArrayIndexOutOfBoundsException();  
  90.   }  
  91.   E data = start.data;  
  92.   start = start.next;  
  93.   size--;  
  94.   return data;  
  95.  }  
  96.    
  97.  public E removeAtLast(){  
  98.   if(size==0){  
  99.    throw new ArrayIndexOutOfBoundsException();  
  100.   }  
  101.   Node<E> tempNode = getNodeAt(size-2);  
  102.   E data = tempNode.next.data;  
  103.   tempNode.next = null;  
  104.   size--;  
  105.   return data;  
  106.  }  
  107.    
  108.  public E removeAt(int position){  
  109.   if(position==0){  
  110.    return removeAtFirst();  
  111.   }else if(position == size-1){  
  112.    return removeAtLast();  
  113.   }else{  
  114.    Node<E> tempNode = getNodeAt(position-1);  
  115.    E data = tempNode.next.data;  
  116.    tempNode.next = tempNode.next.next;  
  117.    size--;  
  118.    return data;  
  119.   }  
  120.  }  
  121.    
  122.  public int size(){  
  123.   return size;  
  124.  }  
  125.    
  126.  public String toString(){  
  127.   if(size==0){  
  128.    return "";  
  129.   }else{  
  130.    StringBuilder output = new StringBuilder();  
  131.    Node<E> tempNode = start;  
  132.    while(tempNode.next!=null){  
  133.     output.append(tempNode.data).append(", ");  
  134.     tempNode = tempNode.next;  
  135.    }  
  136.    output.append(tempNode.data);  
  137.    return output.toString();  
  138.   }  
  139.  }  
  140.    
  141. }  
 
Java代码  收藏代码
 
 
　
　package dsa.linkedlist;    public class Node<E>{   E data;   Node<E> next;  }

 

 
 
Java代码  收藏代码
package dsa.linkedlist;    public class ReverseLinkedListRecursively {        public static void main(String args[]) {          ReverseLinkedListRecursively reverser = new ReverseLinkedListRecursively();          SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);          System.out.println("Original List : " + originalList.toString());          originalList.start = reverser.reverse(originalList.start);          System.out.println("Reversed List : " + originalList.toString());      }        public Node<Integer> reverse(Node<Integer> list) {          if (list == null || list.next == null)              return list;          Node<Integer> nextItem = list.next;          list.next = null;          Node<Integer> reverseRest = reverse(nextItem);          nextItem.next = list;          return reverseRest;      }        private SinglyLinkedList<Integer> getLabRatList(int count) {          SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();          for (int i = 0; i < count; i++) {              sampleList.add(i);          }          return sampleList;      }  }  /*  * SAMPLE OUTPUT Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Reversed List : 9,  * 8, 7, 6, 5, 4, 3, 2, 1, 0  */

 

 
Java代码  收藏代码
 
package dsa.linkedlist;    /**  * This is a singly linked list with no prev pointer.  * @author Braga  * @param <E>  */  public class SinglyLinkedList<E> {      Node<E> start;   int size;      public SinglyLinkedList(){    start = null;    size = 0;   }      //insertAtLast   public void add(E data){    insertAtLast(data);   }      public void insertAtLast(E data){    if(size==0){     start = new Node<E>();     start.next = null;     start.data = data;    }else{     Node<E> currentNode = getNodeAt(size-1);     Node<E> newNode = new Node<E>();     newNode.data = data;     newNode.next = null;     currentNode.next = newNode;    }    size++;   }      public void insertAtFirst(E data){    if(size==0){     start = new Node<E>();     start.next = null;     start.data = data;    }else{     Node<E> newNode = new Node<E>();     newNode.data = data;     newNode.next = start;     start = newNode;    }    size++;   }      public Node<E> getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException{    if(nodePos>=size || nodePos<0){     throw new ArrayIndexOutOfBoundsException();    }    Node<E> temp = start;//Move pointer to front    int counter = 0;    for(;counter<nodePos;counter++){     temp = temp.next;    }    return temp;   }      public void insertAt(int position, E data){    if(position == 0){     insertAtFirst(data);    }else if(position==size-1){     insertAtLast(data);    }else{     Node<E> tempNode = getNodeAt(position-1);     Node<E> newNode = new Node<E>();     newNode.data = data;     newNode.next = tempNode.next;     tempNode.next = newNode;     size++;    }   }      public Node<E> getFirst(){    return getNodeAt(0);   }      public Node<E> getLast(){    return getNodeAt(size-1);   }      public E removeAtFirst(){    if(size==0){     throw new ArrayIndexOutOfBoundsException();    }    E data = start.data;    start = start.next;    size--;    return data;   }      public E removeAtLast(){    if(size==0){     throw new ArrayIndexOutOfBoundsException();    }    Node<E> tempNode = getNodeAt(size-2);    E data = tempNode.next.data;    tempNode.next = null;    size--;    return data;   }      public E removeAt(int position){    if(position==0){     return removeAtFirst();    }else if(position == size-1){     return removeAtLast();    }else{     Node<E> tempNode = getNodeAt(position-1);     E data = tempNode.next.data;     tempNode.next = tempNode.next.next;     size--;     return data;    }   }      public int size(){    return size;   }      public String toString(){    if(size==0){     return "";    }else{     StringBuilder output = new StringBuilder();     Node<E> tempNode = start;     while(tempNode.next!=null){      output.append(tempNode.data).append(", ");      tempNode = tempNode.next;     }     output.append(tempNode.data);     return output.toString();    }   }     }

 


联系
我们