Java 实现单链表反序

  1. //单链表反序  
  2. public class SingleLinkedListReverse {  
  3.       
  4.     public static void main(String[] args) {  
  5.         Node head = new Node(0);  
  6.         Node temp = null;  
  7.         Node cur = null;  
  8.           
  9.         for (int i = 1; i <= 10; i++) {  
  10.             temp = new Node(i);  
  11.             if (i == 1) {  
  12.                 head.setNext(temp);  
  13.             } else {  
  14.                 cur.setNext(temp);  
  15.             }  
  16.             cur = temp;  
  17.         }//10.next = null;  
  18.           
  19.         Node h = head;  
  20.         while (h != null) {  
  21.             System.out.print(h.getData() + “\t”);  
  22.             h = h.getNext();  
  23.         }  
  24.         System.out.println();  
  25.           
  26.         //反转1  
  27. //      h = Node.reverse1(head);  
  28. //      while (h != null) {  
  29. //          System.out.print(h.getData() + “\t”);  
  30. //          h = h.getNext();  
  31. //      }  
  32.           
  33.         //反转2  
  34.         h = Node.reverse1(head);  
  35.         while (h != null) {  
  36.             System.out.print(h.getData() + “\t”);  
  37.             h = h.getNext();  
  38.         }  
  39.           
  40.           
  41.     }  
  42. }  
  43.   
  44. /* 
  45.  * 单链表的每个节点都含有指向下一个节点属性 
  46.  */  
  47. class Node {  
  48.     Object data;//数据对象   
  49.     Node next; //下一节点  
  50.       
  51.     Node(Object d) {  
  52.         this.data = d;  
  53.     }  
  54.     Node(Object d, Node n) {  
  55.         this.data = d;  
  56.         this.next = n;  
  57.     }  
  58.     public Object getData() {  
  59.         return data;  
  60.     }  
  61.     public void setData(Object data) {  
  62.         this.data = data;  
  63.     }  
  64.     public Node getNext() {  
  65.         return next;  
  66.     }  
  67.     public void setNext(Node next) {  
  68.         this.next = next;  
  69.     }  
  70.     //方法1  head被重置  
  71.     static Node reverse1(Node head) {  
  72.   
  73.         Node p = null//反转后新的 头  
  74.         Node q = head;  
  75.         //轮换结果:012,123,234,…. 10 null null  
  76.         while (head.next != null) {  
  77.             p = head.next;      // 第1个 换成第2个  这时p表示原始序列头中的next  
  78.             head.next = p.next;  // 第2个 换成第3个  
  79.             p.next = q;         //已经跑到第1位置的原第2个的下一个 就要变成 原第1个  
  80.             q = p;              //新的第1个 要变成 当前第一个  
  81.         }  
  82.         return p;  
  83.           
  84.     }  
  85.     //方法2 head没重置  
  86.     static Node reverse2(Node head) {  
  87.         //将中间节点的指针指向前一个节点之后仍然可以继续向后遍历链表  
  88.         Node p1 = head, p2 = head.next, p3; // 前 中 后  
  89.         //轮换结果 :012, 123, 234, 345, 456…. 9 10 null  
  90.         while (p2 != null) {  
  91.             p3 = p2.next;    
  92.             p2.next = p1; //指向后 变 指向前  
  93.             p1 = p2;     //2、3向前挪  
  94.             p2 = p3;  
  95.         }  
  96.         head.next = null;//head没变,当输出到0时,再请求0.next 为1  
  97.         return p1;  
  98.     }  
  99. }  

标签