04 -链表相关知识

大多数链表都是检验coding能力的，通过熟练度不断提升。在面试中一二面会进行考察，基本必须AC，是很基础的考察项。

JVM虚拟机里面规定了一个地址为null,然后链表最后一个元素中其实也是存了一个地址，只不过该地址指向null所在的内存空间。所以最后一个元素指向null。（可以理解为启动前约定好，某一个地址就叫null）

1. 链表的遍历
   首先获得头指针，
   循环

   Node cur = head;
   while (cur != null){
   	// 中间处理流程
   	System.out.println(cur.value);
   	//切记不要忘了，更新下一个节点。while循环中一定要更新节点
   	cur = cur.next;
   }
   

2. 反转注意事项：
   定义一个反转方法后， 该方法一定要返回新的头指针，并在调用时进行接收。否则会被GC（引用为0即被GC）。
3. 反转大体步骤
   3.1 先用next记录下一个节点的地址
   3.2 对当前节点的指针进行反转
   3.3.将pre和当前节点head，进行更新 --> 往前移动
   代码：

package class04;

public class linkedList {
   public static class Node {
       public int value;
       public Node next;

       public Node(int value) {
           this.value = value;
       }
   }

   public static class DoubleNode {
       public int value;
       public DoubleNode last;
       public DoubleNode next;

       public DoubleNode(int value) {
           this.value = value;
       }
   }

   // 链表都是需要头节点来进行访问的
   public static Node reverselinkedList(Node head) {
       Node pre = null;
       Node next = null;
       // 修改 Node 中Next指针指向Pre
       // 顺序： 首先保存next, 然后修改指针指向pre，然后将pre和head一同更新到下一个位置
       while (head != null) {
           next = head.next;
           head.next = pre;
           pre = head;
           head = next;
       }
       return pre;
   }

   public static DoubleNode reverseDoubleList(DoubleNode head) {
       DoubleNode pre = null;
       DoubleNode next = null;
       while (head != null) {
           // 1. 先把下一个节点位置 记住
           next = head.next;
           // 2. 修改指针 （此时可以随意修改指针）
           head.last = next;
           head.next = pre;
           // 3.更新pre 和 head
           pre = head;
           head = next;
       }
       return pre;
   }

   public static void printlinkedList(Node head) {
       while (head != null) {
           System.out.println(head.value);
           head = head.next;
       }
   }

   public static void printDoubleList(DoubleNode head) {
       System.out.println("Forward");
       DoubleNode pre = null; // 栈中声明的变量需要赋初值
       while (head != null) {
           System.out.println(head.value);
           pre = head;
           head = head.next;
       }
       System.out.println("Reverse");
       while (pre != null) {
           System.out.println(pre.value);
           pre = pre.last;
       }
   }

   public static void main(String[] args) {
       Node node1 = new Node(1);
       node1.next = new Node(2);
       node1.next.next = new Node(3);
       // 1 -> 2 -> 3

       System.out.println("linked List original order:");
       printlinkedList(node1);
       System.out.println("linked List reverse order:");
       node1 = reverselinkedList(node1);
       printlinkedList(node1);


       DoubleNode head = new DoubleNode(1);
       head.next = new DoubleNode(2);
       head.next.next = new DoubleNode(3);
       head.next.last = head;
       head.next.next.last = head.next;
       // 1 -> 2 -> 3

       System.out.println("Double linked List original order:");
       printDoubleList(head);
       System.out.println("Double linked List reverse order:");
       head = reverseDoubleList(head);
       printDoubleList(head);
   }
}

重点：

1. 栈 ： 后进先出
2. 队列： 先进先出
   那么，对于单链表而言，先出的必定使用head指向，所以根据谁先出，确定head位置。比如，栈，后进先出，那么Head指向后进的。队列，先进先出，那么Head指向先进的。
   所以，
   栈： 只需要head，头插法
   队列： 需要head和tail, 尾插法

特点：
插入，弹出，查看 ----> 时间复杂度 都为O（1）；

并且，单链表无法实现双向队列。
关键点： 在插入或弹出节点时，注意将指针设为空，从而令JVM自动释放引用为0 的 对象。