MySingleList

public class MySingleList implements ILinked{

    //节点
    class Node {
        private int data;
        private Node next;
        public Node(int data) {
            this.data = data;
            //this.next = null;
        }
    }
    private Node head;
    public MySingleList(){
        this.head = null;
    }


    @Override
    public void addFirst(int data) {
        Node node = new Node(data);
        //第一次插入的时候，没有任何的数据节点
        if(this.head == null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }
    }

    @Override
    public void addLast(int data) {
        Node node = new Node(data);
        //write
        if(this.head == null) {
            this.head = node;
        }else {
            Node cur = this.head;
            while(cur.next != null) {
                cur = cur.next;
            }
            //cur所指向的位置就是尾节点
            cur.next = node;
        }
    }
    //检查Index的合法性
    private void checkIndex(int index) {
        if(index < 0 || index > getLength()) {
            throw new UnsupportedOperationException("Index不合法");
        }
    }
    //找到index-1的位置  函数返回该位置的节点引用
    private Node searchIndex(int index) {
        int count = 0;
        Node cur = this.head;
        while(count < index-1){
            cur = cur.next;
            count++;
        }
        return cur;
    }

    @Override
    public boolean addIndex(int index, int data) {
        checkIndex(index);
        //头插法
        if(index == 0) {
            addFirst(data);
            return true;
        }
        Node node = new Node(data);
        Node cur = searchIndex(index);
        node.next = cur.next;
        cur.next = node;
        return true;
    }

    @Override
    public boolean contains(int key) {
        Node cur = this.head;
        while(cur != null) {
            if(cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //查找关键字Key的前驱
    //如果找不到返回null
    private Node searchPre(int key) {
        Node pre = this.head;
        //头结点是要删除的数据节点
        if(pre.data == key) {
            return this.head;
        }
        while(pre.next != null) {
            if(pre.next.data == key) {
                return pre;
            }
            pre = pre.next;
        }
        return null;
    }

    @Override
    public int remove(int key) {
        int oldData = 0;
        Node pre = searchPre(key);
        if(pre == null) {
            throw new UnsupportedOperationException("不存在key节点");
        }
        //是头结点的时候
        if(pre == head && pre.data == key) {
            oldData = this.head.data;
            this.head = this.head.next;
            return oldData;
        }
        Node del = pre.next;
        oldData = del.data;
        pre.next = del.next;
        return oldData;
    }

    @Override
    public void removeAllKey(int key) {
        if(this.head == null) {
            throw new UnsupportedOperationException("单链表为空！") ;
        }
       Node pre=this.head;
       Node cur=this.head.next;
       while(cur!=null){
           if(cur.data==key){
               pre.next=cur.next;
               cur=cur.next;
           }else{
               pre=cur;
               cur=cur.next;
           }
       }
       if(this.head.data==key){
           this.head=this.head.next;
       }
    }

    @Override
    public int getLength() {
        int count = 0;
        Node cur = this.head;
        while(cur != null) {
            count++;
            cur =cur.next;
        }
        return count;
    }

    @Override
    public void display() {
        Node cur = this.head;
        while(cur != null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    public void clear() {
        //this.head = null;
        while(this.head != null) {
            Node cur = this.head.next;
            this.head.next = null;
            this.head = cur;
        }
    }

    public Node ReverseList(){
       Node cur=this.head;
       Node prev=null;
       Node curNext=this.head.next;
       Node reversehead=null;
       while(cur!=null){
           if(curNext==null){
               reversehead =cur;
           }
           cur.next=prev;
           prev=cur;
           cur=curNext;
       }
       return reversehead;
    }
    public Node middleNode(){//找到中间节点
        Node cur=this.head;
        int count=0;
        int count1=getLength()/2;
        while(count<count1){
            cur=cur.next;
            count++;
        }
        return cur;
    }
    //找到单链表中指定倒数第几个节点的数据
    public Node findKthToTail(int k){
        Node fast=this.head;
        Node slow=this.head;
        if(k<=0||k>getLength()){
            return null;
        }
        int count=0;
        while(count!=(k-1)){
            fast=fast.next;
            count++;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    //取得节点内的数据
    public static int getData(Node node){
        int cur=node.data;
        return cur;
    }
    //单链表的逆置
    public Node reverseList() {
       /* Node cur = this.head;
        Node prev = null;
        Node reverseHead = null;
        while(cur != null) {
            Node curNext = cur.next;
            if(curNext == null) {
                reverseHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return reverseHead;*/
       Node cur=this.head;
       Node pre=null;
       Node newHead=null;
       while(cur!=null){
           Node curNext=cur.next;
           if(curNext==null){
               newHead=cur;
           }
           cur.next=pre;
           pre=cur;
           cur=curNext;
       }
       return newHead;
    }
    public void show(Node resHead) {
        Node cur = resHead;
        while(cur != null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //取得数据 将单链表划分为大于X的数据段和小于X的数据段
    public Node oartition(int x){
        Node beforeStar=null;
        Node beforeEnd=null;
        Node afterStar=null;
        Node afterEnd=null;
        Node pHead=this.head;
        while(pHead.next!=null){
            if(x<pHead.data) {
                if (beforeStar == null) {
                    beforeStar = pHead;
                    beforeEnd = beforeStar;
                } else {
                    beforeEnd.next=pHead;
                }
            }
            if(x>pHead.data ){
              if(afterStar ==null){
                  afterStar =pHead;
                  afterEnd=beforeStar;
              }else{
                  afterEnd.next=pHead;
              }
            }
        }
        if(beforeStar ==null){
            return afterStar ;
        }
        beforeEnd.next=afterStar ;
        return beforeStar ;

    }
    //在单链表中制造一个环
    public boolean creatLoop(){
        Node cur=this.head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=this.head.next.next.next;
        return true;


    }
    //测试单链表中是否有环
    public boolean hasCycle() {
        Node fast=this.head;
        Node slow=this.head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    //输出单链表中环的入口
    public Node detectCycle() {
       /* Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if(fast==null||fast.next==null) {
            return null;
        }else {
            slow = this.head;
            while (slow == fast) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return slow;*/
       Node slow=this.head;
       Node fast=this.head;
       while(fast!=null&&fast.next!=null){
           slow=slow.next;
           fast=fast.next.next;
           if(slow==fast){
               break;
           }
       }
       if(fast==null||slow==null){
           return null;
       }else{
           slow=this.head;
           while(slow==fast){
               slow=slow.next;
               fast=fast.next;
           }
       }
       return slow;

    }
    //删除单恋链表中所有重复的节点
    public Node deletaP(){
        Node cur=this.head;
        Node newHead=null;
        Node tmpHead=newHead;
        while(cur!=null){
            if(cur.next!=null&&cur.data==cur.next.data){
                while(cur.next!=null&&cur.data==cur.next.data){
                    cur=cur.next;
                }
                cur=cur.next;
                newHead.next =cur;
            }else{
                newHead .next=cur;
                newHead=cur;
                cur=cur.next;
            }
        }
        return tmpHead.next;

    }
    //回文序列
    public Node isHuiWen(){
        Node slow=this.head;
        Node fast=this.head;
        while(fast.next!=null||fast!=null){
                fast = fast.next.next;
                slow = slow.next;
        }
        Node p=slow.next;
       Node pNext=p.next;
       while(p!=null){

       }
       return p;
    }
    //判断两个单链表是否相交 有没有公共节点   两个单链表相交只可能是Y型
    //如果一个单链表长 一个短   让长的先走到一样
  public static Node isSame(Node headA,Node headB){
        Node pLong=headA;
        Node pShort=headB;
        int lenA=0;
        while(pLong!=null){
            lenA++;
            pLong=pLong.next;
        }
        int lenB=0;
        while(pShort!=null){
            lenB++;
            pShort=pShort.next;
        }
        int len=lenA-lenB;
        if(len<0){
            pLong=headB;
            pShort=headA;
            len=lenB-lenA;
        }
        while(pLong !=null&&pShort !=null&&pLong!=pShort){

        }
        if(pLong !=null&&pShort !=null&&pShort ==pLong ){
            return pLong;
        }
        return null;
  }
  public static void creatCut(Node headA,Node headB){
        headA.next.next=headB.next.next;
  }
    public Node returnHead(){
        return this.head;
    }


}