import java.util.Stack;
class Nodes{
    int data ;
    Nodes next;
    Nodes(){}
    Nodes(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkeNodes{
    //create
  public  Nodes create(){
       Nodes head = new Nodes();
       Nodes p = head;
       for(int i=0;i<5;i++) {
           p.next = new Nodes();
           p.next.data = i+1;
           p = p.next;
       }
       return head;
    }
  //用栈实现从尾到头输出链表
   public void printRev(Nodes head){
      if(head==null) return ;
      Nodes p = head.next;
      Stack s = new Stack(); 
      while(p!=null) {
          s.push(p);
          p = p.next;
      }
      while(!s.empty()){
          Nodes n = (Nodes)s.pop();
          System.out.print(n.data + " ");
      }
   }
   //用递归实现倒输出链表
   void printResByBack(Nodes head){
       if(head!=null) {
           if(head.next!=null) {
               printResByBack(head.next);
           }
           System.out.print(head.data + " ");
       }
   }
// 打印链表 
   static void print(Nodes head){
       while(head!=null) {
           System.out.print(head.data+" ");
           head = head.next;
       }
   }


**//deleteNode() O(1)= ((n-1)*O(1) + O(n)/2)
    static void deleteNode(Nodes head,Nodes x){
        if(head == null || x == null)
            return ;
        //不是尾节点
        if(x.next!=null){
            Nodes temp = x.next;
            x.next = temp.next;
            x.data = temp.data;
        }
        //只有一个节点，，头结点（尾节点）
        else if(head == x){
            head = null;
        }else {
            //尾节点
            x = null;
        }
    }
}**  

    **//链表倒置
    static Nodes linkedTableRecursively(Nodes head) {
        if(head == null) 
            return null;
        Nodes pNode = head,recHead = null;
        Nodes pre = null;
        Nodes pNext = null;
        while(pNode!=null) {
            pNext = pNode.next;
            if(pNode.next == null) 
                recHead = pNode;
            pNode.next = pre;
            pre = pNode;
            pNode = pNext;
        }
        return recHead;
    }**


public class Linke {
  public static void main(String[] args) {
    LinkeNodes lk = new LinkeNodes();
    Nodes head = lk.create();
    /*System.out.print("stack实现："); lk.printRev(head); System.out.print("\n递归实现："); lk.printResByBack(head.next);*/
    lk.print(head);
    lk.deleteNode(head,new Nodes(2));

}
}

删除节点两种方法：
1、从头结点开始遍历，找到待删除的节点q的前驱p，让p指向q的下一个节点。
2、直接用待删除q的下一个节点来覆盖节点q，这样就相当于删除节点q了，时间 复杂度为O（1）。（这种是基于一个假设:待删除节点在链表中，实际上我们需要花费O(n)的时间来判断待删除节点 是否在表中，受到O(1)的限制，我们不得不把确保节点在表中交给方法的调用者）