Java带头节点单链表的增删合并以及是否有环

男娘i 2021-12-14 06:57 79阅读 0赞

**带头节点单链表**

**1.优势：**

1）当链表为空时，指针指向头结点，不会发生null指针异常

2）方便特殊操作（删除第一个有效节点或者插入一个节点在表头）

3）单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。

4）代码更加简单易懂

**2.相关操作**

**1）建立单链表 即建立一个头结点**

static class Entry<T> {
            T data; // 链表节点的数据域
            Entry<T> next; // 下一个节点的引用
    
            public Entry(T data, Entry<T> next) {
                this.data = data;
                this.next = next;
            }
    
        }
    
        /**
         * 头节点的类型
         *
         * @param <T>
         */
        private static class HeadEntry<T> extends Entry<T> {
            int cnt; // 用来记录节点的个数
    
            public HeadEntry(int cnt, T data, Entry<T> next) {
                super(data, next);
                this.cnt = cnt;
            }
        }

**2）头插：新建节点next域指向头结点的next域，再将头结点next指向新节点。**

public void insertHead(T val) {
            Entry<T> newNode = new Entry<>(val, null);
            newNode.next = this.head.next;
            this.head.next = newNode;
        }

**3）尾插：从头结点开始遍历，当next出现null时，已经到达尾部，将next指向新节点即可**

public void insertTail(T val) {
            Entry<T> temp = this.head;
            Entry<T> newNode = new Entry<>(val, null);
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }

**4）删除值为val的节点 ：设置一前一后指针进行遍历，当后指针发现值为val的节点时，前指针的next域指向后指针的next域即可**

public void remove(T val) {
            Entry<T> frontTemp = this.head;
            Entry<T> temp = frontTemp.next;
            while (temp.data != val) {
                frontTemp = frontTemp.next;
                temp = temp.next;
            }
            frontTemp.next = temp.next;
        }

**5）逆置单链表 :将第二个有效节点不断进行头插操作，就会产生逆置效果**

**    将链表从第二个有效节点开始一分为二，不断头插进前一链表 **

public void reverse() {
            if (this.head.next == null) {
                return;
            }
            Entry<T> cur = this.head.next.next;
            this.head.next.next = null;
            Entry<T> post = null;
            while (cur != null) {
                post = cur.next;
                cur.next = head.next;
                head.next = cur;
                cur = post;
            }
        }

**6）获取倒数第k个节点的值：设置两个相距K的指针，当前指针到达链表尾部时，前指针指向倒数第k个节点**

public T getLastK(int k) {
            Entry<T> cur1 = this.head.next;
            Entry<T> cur2 = cur1.next;
            for (int i = 1; i < k; i++) {
                cur2 = cur2.next;
                if (cur2 == null) {
                    return null;
                }
            }
            while (cur2 != null) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1.data;
        }

**7）判断链表是否有环，如果有，返回入环节点的值；否则返回null：**

**设置快慢指针，快指针一次移动两次，慢指针一次移动一次，如果出现快指针指向的节点等于慢指针指向的节点 ，即证明节点有环。**

**入环节点的求法：**

![1641726-20190622101016350-1888075717.png][]

**设相遇点为A点；当快指针经过 x+2y+z个节点时时 慢指针走了x+y个节点   可得2（x+y）=x+2y+z   化简可得x=z；所以**

**fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点**

public T isLinkCircle() {
            //利用快慢指针检测是否有环
            Entry<T> slow = this.head.next;
            Entry<T> quick = this.head.next;
            while (quick != null && quick.next != null) {
                slow = slow.next;
                quick = quick.next.next;
                if (slow == quick) {
                    break;
                }
            }
            if (quick == null) {
                return null;
            } else {
                // fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点
                quick = this.head.next;
                while (quick != slow) {
                    quick = quick.next;
                    slow = slow.next;
                }
                return slow.data;
            }
        }

**8)合并两个有序单链表**

public void merge(Link<T> link) {
            Entry<T> p = this.head;
            Entry<T> p1 = this.head.next;
            Entry<T> p2 = link.head.next;
    
            // 比较p1和p2节点的值，把值小的节点挂在p的后面
            while (p1 != null && p2 != null) {
                if (p1.data.compareTo(p2.data) >= 0) {
                    p.next = p2;
                    p2 = p2.next;
                } else {
                    p.next = p1;
                    p1 = p1.next;
                }
                p = p.next;
            }
            if (p1 != null) { // 链表1还有剩余节点
                p.next = p1;
            }
    
            if (p2 != null) { // 链表2还有剩余节点
                p.next = p2;
            }
        }

**总源代码**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

class Link<T extends Comparable<T>> {
    
        // 指向单链表的第一个节点
        Entry<T> head;
    
        public Link() {
            this.head = new Entry<>(null, null);
        }
    
        /**
         * 单链表的头插法
         *
         * @param val
         */
        public void insertHead(T val) {
            Entry<T> newNode = new Entry<>(val, null);
            newNode.next = this.head.next;
            this.head.next = newNode;
        }
    
        /**
         * 单链表的尾插法
         *
         * @param val
         */
        public void insertTail(T val) {
            Entry<T> temp = this.head;
            Entry<T> newNode = new Entry<>(val, null);
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    
        /**
         * 单链表中删除值为val的节点
         *
         * @param val
         */
        public void remove(T val) {
            Entry<T> frontTemp = this.head;
            Entry<T> temp = frontTemp.next;
            while (temp.data != val) {
                frontTemp = frontTemp.next;
                temp = temp.next;
            }
            frontTemp.next = temp.next;
        }
    
        /**
         * 逆置单链表
         */
        public void reverse() {
            if (this.head.next == null) {
                return;
            }
            Entry<T> cur = this.head.next.next;
            this.head.next.next = null;
            Entry<T> post = null;
            while (cur != null) {
                post = cur.next;
                cur.next = head.next;
                head.next = cur;
                cur = post;
            }
        }
    
        /**
         * 获取倒数第K个单链表节点的值
         * 1.遍历一次链表，统计链表节点的个数length
         * 2.length-k
         * 只遍历一次链表，找出数
         *
         * @param k
         */
        public T getLastK(int k) {
            Entry<T> cur1 = this.head.next;
            Entry<T> cur2 = cur1.next;
            for (int i = 1; i < k; i++) {
                cur2 = cur2.next;
                if (cur2 == null) {
                    return null;
                }
            }
            while (cur2 != null) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1.data;
        }
    
        /**
         * 判断链表是否有环，如果有，返回入环节点的值；否则返回null
         *
         * @return
         */
        public T isLinkCircle() {
            //利用快慢指针检测是否有环
            Entry<T> slow = this.head.next;
            Entry<T> quick = this.head.next;
            while (quick != null && quick.next != null) {
                slow = slow.next;
                quick = quick.next.next;
                if (slow == quick) {
                    break;
                }
            }
            if (quick == null) {
                return null;
            } else {
                // fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点
                quick = this.head.next;
                while (quick != slow) {
                    quick = quick.next;
                    slow = slow.next;
                }
                return slow.data;
            }
        }
    
        /**
         * 打印单链表的所有元素的值
         */
        public void show() {
            Entry<T> temp = this.head.next;
            while (temp != null) {
                System.out.print(temp.data + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    
    
        /**
         * 单链表的节点类型
         *
         * @param <T>
         */
        static class Entry<T> {
            T data; // 链表节点的数据域
            Entry<T> next; // 下一个节点的引用
    
            public Entry(T data, Entry<T> next) {
                this.data = data;
                this.next = next;
            }
    
        }
    
        /**
         * 头节点的类型
         *
         * @param <T>
         */
        private static class HeadEntry<T> extends Entry<T> {
            int cnt; // 用来记录节点的个数
    
            public HeadEntry(int cnt, T data, Entry<T> next) {
                super(data, next);
                this.cnt = cnt;
            }
        }
    
        /**
         * 合并两个有序的单链表
         *
         * @param link
         */
    
        public void merge(Link<T> link) {
            Entry<T> p = this.head;
            Entry<T> p1 = this.head.next;
            Entry<T> p2 = link.head.next;
    
            // 比较p1和p2节点的值，把值小的节点挂在p的后面
            while (p1 != null && p2 != null) {
                if (p1.data.compareTo(p2.data) >= 0) {
                    p.next = p2;
                    p2 = p2.next;
                } else {
                    p.next = p1;
                    p1 = p1.next;
                }
                p = p.next;
            }
            if (p1 != null) { // 链表1还有剩余节点
                p.next = p1;
            }
    
            if (p2 != null) { // 链表2还有剩余节点
                p.next = p2;
            }
        }
    }

转载于:https://www.cnblogs.com/jiezai/p/11063304.html

[1641726-20190622101016350-1888075717.png]: /images/20211213/a97cad2cd3a146748b41cbca97823821.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/d08222dd54a5401a9ee568917c4c864a.png