有关单链表的一些习题

野性酷女 2021-09-23 07:02 322阅读 0赞

/**
     * @auther: 巨未
     * @DATE: 2018/12/28 0028 20:27
     * @Description: 单链表
     */
    class LinkDemo {
        class Entry { //用实例内部类写  节点
            int data;
            Entry next;//next域为节点类型:有数据和next
    
            public Entry() {  //头节点的构造函数
                this.data = -1;
                this.next = null;
            }
    
            public Entry(int val) { //数据节点
                this.data = val;
                this.next = null;
            }
        }
    
        private Entry head = null;//代表头节点的引用地址
    
        public LinkDemo() {
            this.head = new Entry(); // 得到头节点的地址引用
        }
    
        //头插法
        public void insertHead(int val) {
            Entry entry = new Entry(val);
            entry.next = this.head.next;
            this.head.next = entry;
        }
    
        //尾插法
        public void insertTail(int val) {
            Entry cur = this.head;
            while (cur.next != null) {
                cur = cur.next;  //cur++
            }
            Entry entry = new Entry(val);
            cur.next = entry;
        }
        //任意位置插入
    
        public boolean insertPos(int pos, int val) {
            if (pos < 0 || pos > getLinkLength()) {
                return false;
            }
            //找到pos-1位置的节点地址：定义一个cur，找到pos位置
            Entry cur = this.head;
            for (int i = 0; i <= pos - 1; i++) {
                cur = cur.next;
            }
            //进行插入    cur是pos位置的前一个节点
            Entry entry = new Entry(val);
            entry.next = cur.next;  //把cur的next给entry的next
            cur.next = entry;  //把entry给cur的next
            return true;
        }
    
        /**
         * 链表的长度
         * @return
         */
        public int getLinkLength() {
            int count = 0;
            Entry cur = this.head.next;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }
    
        //查找关键字key的前驱
        public Entry searchKey(int key) {
            Entry cur = this.head;
            while (cur.next != null) {
                if (cur.next.data == key) {
                    return cur;
                }
                cur = cur.next;//cur++
            }
    
            return null;
        }
    
        //删除关键字key:使key的前驱的next域指向key后一个节点的地址
        public boolean deleteKey(int key) {
            Entry cur = searchKey(key);
            if (cur == null) {
                return false;
            }
            Entry delete = cur.next;
            cur.next = delete.next;
            return true;
        }
    /*
    * show函数  show2函数
    */
        public void show() {
            Entry cur = this.head.next;
            while (cur != null) {
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        public void show2(Entry rehead) {
            Entry cur = rehead;
            while (cur.next != null) {
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        //删除值为val的所有节点(时间复杂度O（n）
        public void deleteAllkey(int key) {
            // pre 等于 head    cur 等于 head.next  说明这个链表有数据
            Entry pre = this.head;
            Entry cur = this.head.next;
            while (cur != null) {
                if (cur.data == key) {
                    pre.next = cur.next;
                    cur = cur.next;// cur = pre.next;
                } else
                    pre = cur;
                cur = cur.next;
            }
        }
    
        //以最快的时间查找倒数第K个节点(只遍历单链表一次
        public int lastK(int K) {
            if (K <= 0 || K > getLinkLength()) {
                return -1;
            }
            Entry pre = this.head;
            Entry cur = this.head;
            while (K - 1 > 0) { //从倒数第一个开始有效
                cur = cur.next;
                if (cur != null) { //当cur
                    K--;
                } else {
                    System.out.println("没有倒数第K个节点");
                    return -1;
                }
            }
            while (cur.next != null) {
                pre = pre.next;
                cur = cur.next;
            }
            return pre.data;
        }
    
        //以最快速度删除倒数第K个节点：找到K节点的前驱。cur先走K步
        public void deleteK(int K) {
            if (K <= 0) {
                return;
            }
            Entry pre = this.head;
            Entry cur = this.head;
            while (K > 0) {
                cur = cur.next;
                if (cur != null) {
                    K--;
                } else {
                    System.out.println("没有倒数第K个节点");
                    return;
                }
            }
            while (cur.next != null) {  //pre和cur同时向后走
                pre = pre.next;
                cur = cur.next;
            }
            Entry delete = pre.next;
            pre.next = delete.next;
        }
    
        //！！！逆置单链表：
        // 1.采用头插法2.单链表的反转
        public void reverseLink1() {
            Entry cur = this.head.next;
            this.head.next = null;//将第一个节点的next置位null，成为最后一个节点。然后开始把后面的节点进行头插
    
            while (cur != null) {
                Entry curNext = cur.next;
                cur.next = this.head.next;
                this.head.next = cur;
                cur = curNext;
            }
        }
    
        //2.单链表的反转:
        public Entry reverseLink2() {
            Entry reverseHead = null;
            Entry prev = null;   // prev为null,赋给头结点的next
            Entry cur = this.head; //cur为头结点
    
            while (cur != null) { // 遍历
                Entry curNext = cur.next;
                if (curNext == null) {
                    reverseHead = cur;  //cur的next为空则cur为反转过来的头结点
                }
                cur.next = prev;  //第一个的next为null
                prev = cur;  //
                cur = curNext;
    
            }
            return reverseHead;
        }
    
        //判断单链表是否有环：
        // 1.创建一个环
        public void creatLoop() {
            Entry cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = this.head.next.next;// 尾节点的next指向第二个节点的next，有环
        }
    
        //2.判断是否有环：fast走两步，slow走一步，两个终会相遇成环
        public boolean isLoop() {
            Entry fast = this.head;
            Entry slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    System.out.println(fast.data + slow.data + "成环");
                    return true;
                }
            }
            return false;
        }
    
        //如果有环：求出入口点：假设链表长为n,slow每次走X，fast每次走Y，在环里相遇，n+Y = 2（X+Y）→X+X+Y = n。
        public int entrance() {
            Entry fast = this.head;
            Entry slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {//如果相遇，让slow回到头结点，slow和fast各走一步。再次相遇的点则为入口点
                    break;
                }
            }
            if (fast == null || fast.next == null) {
                return -1;
            }
            slow = this.head;
            while (fast != slow) {
                slow = slow.next;
                fast = fast.next;
            }
            System.out.println(fast.data);
            return fast.data;
        }
    
        //求环的长度： 在环中相遇，定义一个计数器count=1（让slow先走一步，不然slow和fast永远相等），fast不变，slow走一步计数器++。再次相遇时返回计数器的值
        public int loopLength() {
            Entry fast = this.head;
            Entry slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (slow == fast) {
                    break;
                }
                if (fast == null || fast.next == null) {
                    return -1;
                }
                slow = slow.next;
                int count = 1;
                while (fast != slow) {
                    count++;
                    slow = slow.next;
                }
                return count;
            }
        return 0;
        }
    
        public Entry getHead() {
            return head;
        }
    }
    
    public class TestLinkDemo {
    
        //判断两个长度不相等的单链表，是否相交，相交求交点？(相交：地址相同)
        public static void creatCutLink(LinkDemo link1,LinkDemo link2){ //创造相交
            LinkDemo.Entry head1 = link1.getHead();
            LinkDemo.Entry head2 = link2.getHead();
            head1.next.next = head2.next.next.next;//先创造相交
        }
        public static boolean isCut(LinkDemo link1,LinkDemo link2) {  //判断是否相交
            LinkDemo.Entry head1 = link1.getHead();
            LinkDemo.Entry head2 = link2.getHead();
            int len1 = link1.getLinkLength();
            int len2 = link2.getLinkLength();
            int len = len1 - len2;
            if (len < 0) {       //保证head1指向最长的那个链表
                head1 = link2.getHead();
                head2 = link1.getHead();
                len = len2 - len1;    //更新len的值，
            }
            for (int i = 0; i < len; i++) {
                head1 = head1.next;
    
           /* if (len1 > len2) {  //长度长的链表减去短的链表的长度之后   长链表先走减数步  然后在一起走
                len = len1 - len2;
                while (head1 != null) {
                    for (int i = 0; i < len; i++) { //link1长，先走减数步
                        head1 = head1.next;
                    }
                }
            } else {
                len = len2 - len1;
                while (head2 != null) {
                    for (int j = 0; j < len; j++) {  //link2长，先走减数步
                        head2 = head2.next;
                    }
                }
            }*/
                while (head1 != head2 && head1 != null && head2 != null) {  //一起走
                    head1 = head1.next;
                    head2 = head2.next;
                }
                if (head1 == head2 && head1 != null) {     //相等则相交
                    return true;
                } else
                    return false;
            }
                return false;
    
        }
    
        /*
        * 合并两个有序的单链表(1.确定合并之后新的单链表的头部newhead，p1指向第一个链表的第一个数据节点，
        *                                                             p2指向第二个链表的第一个数据节点，比较p1和p2的data，谁小则新链表的头部为谁
        *
        */
        public static LinkDemo.Entry mergeLink(LinkDemo link1,LinkDemo link2) {
            //1.找到合并之后新的链表的头部
            LinkDemo.Entry newHead = null;
            LinkDemo.Entry p1 = link1.getHead().next;
            LinkDemo.Entry p2 = link2.getHead().next;
          if (p1.data < p2.data) {
              newHead = link1.getHead();
          }else {
              newHead = link2.getHead();
          }
          //串联链表的节点！**不能动newHead      p1和p2的值比较
    
            LinkDemo.Entry tmpHead = newHead;  //建一个临时head，穿针引线，寻找链表的路径
    
            while(p2 != null && p1 != null) {   //并且&&
                if (p1.data < p2.data) {   //比较之后谁的数值小，谁走
                    tmpHead.next = p1;
                    p1 = p1.next;
                }else{
                    tmpHead.next = p2;
                    p2 = p2.next;
                }
                tmpHead = tmpHead.next;//循环一次，tmpHead更新一次
    
                if(p1 != null){
                    tmpHead.next = p1;
                }
                if(p2 != null){
                    tmpHead.next = p2;
                }
            }
            return newHead;
        }
        //重新写一个show函数
        public static void showMerge(LinkDemo.Entry newHead) {
            LinkDemo.Entry cur = newHead.next;
            while(cur != null) {
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
    
        //删除奇数节点？？？？？？
    
        public static void main(String[] args) {
              LinkDemo link1 = new LinkDemo();
              for (int i = 0; i < 5; i++) {
                link1.insertTail(i);//尾插  正序
            }
            LinkDemo link2 = new LinkDemo();
            for (int i = 4; i < 10; i++) {
                link2.insertTail(i);
            }
            mergeLink(link1,link2);
            showMerge(link1.getHead());
        }
    
        public static void main1(String[] args) {
            LinkDemo linkDemo = new LinkDemo();
           /*for (int i = 0; i < 10; i++) {
                linkDemo.insertHead(i);//头插  倒序
            }
            linkDemo.show();*/
            for (int i = 0; i < 10; i++) {
                linkDemo.insertTail(i);//尾插  正序
            }
            linkDemo.show();
            linkDemo.insertPos(2,6);
            linkDemo.show();
    //        linkDemo.deleteKey(0);
    //        linkDemo.show();
    //        linkDemo.deleteAllkey(6);
    //        linkDemo.show();
    //        linkDemo.lastK(9);
    //        linkDemo.deleteKey(1);
    //        linkDemo.show();
    //        linkDemo.reverseLink1();  //第一种逆置方法
    //        linkDemo.show();
    //        linkDemo.show2(linkDemo.reverseLink2()); //第二种逆置方法
            linkDemo.creatLoop();
            if(linkDemo.isLoop()){
                System.out.println("有环");
            }else
                System.out.println("无环");
            linkDemo.entrance();
        }
    }