Java集合中的链表与结构详解

目录

• 一、链表概念与结构
• 二、当向单链表的实现
• 2.1 准备工作
• 2.2 初始化链表
• 2.3 打印数据、链表长度、查找数据
• 2.4 头插法
• 2.5 尾插法
• 2.6 任意位置插入节点
• 2.7 删除第一次出现 key 的节点
• 2.8 删除链表中所有数据为 key 的节点
• 2.9 清空
• 三、面试题
• 3.1 删除链表中等于给定值 key 的所有节点。（与上面的 2.8 一个意思）
• 3.2反转一个单链表。
• 3.3返回链表中的中间节点，如果有两个中间节点，则返回第2个节点。
• 3.4输出该链表中倒数第 k 个节点。
• 3.5合并两个有序链表并按升序排序成有序链表返回。
• 3.6以 x 值为基准将链表分割成两部分，所有小于 x 的节点排在大于或等于 x 的节点之后。
• 3.7判断是否为回文链表。
• 3.8输入两个链表，找出它们的公共节点。
• 3.9判断链表中是否有环。* 进阶：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

前情提要：在学习 ArrayList 时，认识到由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景。因此：Java 集合中又引入了LinkedList，即链表结构。

一、链表概念与结构

        链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序的通过链表中的引用链接次序实现的。

其结构总共有8种：

        带头链表中的第一个节点相当于一个标记，如果采用头插法新增节点，只能在当前头的下一个节点插入；而如果是不带头的链表，头插法是在第一个节点前面新增节点。

二、当向单链表的实现

整个实现将围绕下图展开：

        定义一个 cur 对象，表示当前节点。用法：遍历链表。

注意

1、cur 为空和 cur.next 为空的区别。     

2、单向链表不能回退。

2.1 准备工作

        1、先定义一个类用来表示整个链表，名为 SingleLinkedList。

        2、而链表中包含节点，每个节点带有两个域，一个是数据域存储整型数据；另一个是指针域，指针域中存放的是下一个 节点 的引用，因此其类型也就是节点；且注意两个属性都用 public 修饰，在测试时大有用途。将每个节点封装成链表的内部类。

        3、定义一个头部节点，用于查找或者输出链表数据，但这里并不代表链表带头。

        4、将对链表的操作封装成一个接口，其功能包括打印链表数据 display、计算链表长度 size、查找数据 contains、头插法插入数据 addFirst、尾插法插入数据 addLast、任意位置插入数据 addIndex、删除第一次出现 key 的节点 remove、删除所有值为 key 的节点 removeAllKey、清空。

SingleLinkedList 链表：

package test;
// 不带头 单向 链表
public class SingleLinkedList implements ILink{
    static class ListNode{   // 每一个 节点 都是对象，具有共同属性，因此可以抽象成内部类
        public int val;
        public ListNode next;  // 节点的地址，类型也应该是节点的类型
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;  // 头节点
    @Override
    // ......
}

ILink 接口：

package test;
/**
 * 链表的操作
 */
public interface ILink {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    // 清空
    void clear();
    // 打印链表数据
    void display();
}

        在实现具体的操作之前，还需要考虑链表是否为空，即 head == null ?

2.2 初始化链表

        在具体实现各项功能之前，需要有一个原始的链表，利于展示操作效果。其定义方法如下

package test;
public class SingleLinkedList implements ILink{
    // ......
    public void creatList(){  // 创建一个原始链表
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    // ......
}

2.3 打印数据、链表长度、查找数据

        这三个功能都需要将链表从头到尾遍历一遍。而遍历的条件只是当前节点不为空。

package test;
public class SingleLinkedList implements ILink{
    // ......
    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();   // 换行
    }
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
}

package test;
public class TestSingle {
    public static void main(String[] args) {
        // ILink iLink = new SingleLinkedList(); // 通过接口无法调用 creatList()
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.creatList();  // 还没实现新增节点功能前调用的原始链表
        linkedList.display();
        System.out.println(linkedList.size());
    }
}

2.4 头插法

@Override
public void addFirst(int data) {
    ListNode newNode = new ListNode(data);
    newNode.next = head;
    this.head = newNode;
}

        即使原先的链表是空的，代码一样能实现头插法插入节点。

2.5 尾插法

@Override
public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    if (head == null){  // 原来链表中一个节点都没有的情况下
        head = newNode;
        return;
    }
    ListNode cur = head;
    while (cur.next != null){
        cur = cur.next;
    }  // 循环走完说明 cur.next == null 了
    cur.next = newNode;
}

package test_8_7;
public class TestSingle {
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        // 实现新增节点功能之后，不需要调用 creatList()，也可以创建链表
        // 头插法
        linkedList.addFirst(11);
        linkedList.addFirst(22);
        linkedList.addFirst(33);
        linkedList.addFirst(44);
        // 尾插法
        linkedList.addLast(55);
        linkedList.display();
        System.out.println(linkedList.size());
    }
}

2.6 任意位置插入节点

注意

1、指定位置的合法性；

2、指定下标为 0 和 指定位置等于链表长度 的情况分开处理；

3、单向链表不能回退，因此注意 cur 的位置；

4、所有的插入，优先绑定后面的节点。

    @Override
    public void addIndex(int index, int data) throws IllegalIndexException{
        int len = this.size();  // 存储当前长度，好处：提高效率
        if (index < 0 || index > len){
            throw new IllegalIndexException("指定位置不合法！！！");
        }else {
            if (index == 0){
                this.addFirst(data);
                return;
            }
            if (index == len){
                this.addLast(data);
                return;
            }
            ListNode newNode = new ListNode(data);
            ListNode cur = head;
            while (index - 1 != 0){
                cur = cur.next;
                index--;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    }

package test;
// 处理指定位置的不合法异常
public class IllegalIndexException extends RuntimeException{
    public IllegalIndexException(){
    }
    public IllegalIndexException(String msg){
        super(msg);
    }
}

2.7 删除第一次出现 key 的节点

    @Override
    public void remove(int key) {
        if (head == null){
            return;
        }
        if(head.val == key){
            head = null;
        }
        ListNode cur = findNodeOfKey(key);
        if (cur == null){
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    public ListNode findNodeOfKey(int key){  // 找到存储的数据是key的对象，并返回
        ListNode cur = head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

提示

1、在链表中查找 key 可封装成一个方法

2、查找 key 的条件 cur.next 不为空的前提下，已经判断了 cur.next 存储的数据是否等于 key 了

2.8 删除链表中所有数据为 key 的节点

    @Override
    public void removeAllKey(int key) {
        if (head == null){
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null){
            if (cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key){
            head = head.next;
        }
    }

2.9 清空

        像之前“清空” ArrayList 的方法在链表中是不可行的，因为如果引用一直存在，那么引用所指的对象无法被内存回收，容易造成内存泄漏，因此只有将 next 都置空了才算清空了链表数据。

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

三、面试题

3.1 删除链表中等于给定值 key 的所有节点。（与上面的 2.8 一个意思）

3.2反转一个单链表。

    public ListNode reverseList() {  // 反转
        if(head == null){
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNode = cur.next;
            cur.next = head;
            head = cur;
            cur = curNode;
        }
        return head;
    }

3.3返回链表中的中间节点，如果有两个中间节点，则返回第2个节点。

提示，不能通过计算链表长度的方法进行编程。

那么，采用双指针的方法，快指针走两步，慢指针走1步，最后慢指针指向的就是中间。

    public ListNode middleNode() {  // 找中间节点
      python  ListNode fast = head;  // 快指针，走两步
        ListNode slow = head;  // 慢指针，走一步
        while(fast != null && fast.next != null){  // &&前面必须是 fast != null 的条件
            fast = fast.next.next;
            slow = slow.next;
        }
        /*while(fast.next != null && fast != null){  // 输出 NullPointerException
            fast = fast.next.next;
            slow = slow.next;
        }*/
        return slow;
    }

3.4输出该链表中倒数第 k 个节点。

        虽然 leetcode 上已经保证了 k 的合法性，但自己实现的时候还是需要注意 k 的有效范围。

    public int kthToLast(int k) {  // 返回倒数第k个字节的数据
        if(head == null){
            return -1;
        }
        // 注意k的范围
        if (k <= 0){
            return -1;
        }
        /*if (k > 5){  // 这样写还得求链表的长度，不好
            return -1;
        }*/
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while(count != k-1){  // 为了与慢指针拉开一定的距离
            fast = fast.next;
            if(fast == null)  // 这里就是判断k是否超出链表长度的条件
                return -1;
            count++;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

3.5合并两个有序链表并按升序排序成有序链表返回。

提示

1、创建一个头节点，作为标志，可存储数据，但该数据无实际意义；

2、返回的节点不是创建的头节点。

3、在自己实现的链表中实现时，需要注意，因为该方法操作的是两个链表，因此不好将它定义到 SingleLinkedList 这个类中，因此直接定义到测试类。但直接定义到测试类时因为 ListNode 是 SingleLinkedList 的内部类，需要用 SingleLinkedList. 来调用 ListNode

package test;
public class TestSingle {
    public static SingleLinkedList.ListNode mergeTwoLists
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) { // 合并两个有序链表并排序
        SingleLinkedList.ListNode newHead = new SingleLinkedList.ListNode(-1); // 随便传一个数据，因为这个数据无效
        SingleLinkedList.ListNode tmp = newHead;
        while(headA != null && headB != null){
            if (headA.val < headB.val){
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else{
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null){
            tmp.next = headA;
        }
        if (headB != null){
            tmp.next = headB;
        }
        return newHead.next;
    }
    public static void main(String[] args) {
        // 测试合并两个链表
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(4);
        linkedList.addLast(11);
        linkedList.addLast(19);
        linkedList.addLast(44);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addFirst(3);
        linkedList2.addLast(6);
        linkedList2.addLast(32);
        linkedList2.addLast(57);
        SingleLinkedList.ListNode newNode = mergeTwoLiwww.devze.comsts(linkedList.head, linkedList2.head);
        linkedList.display(newNode);
    }
}

3.6以 x 值为基准将链表分割成两部分，所有小于 x 的节点排在大于或等于 x 的节点之后。

    public ListNode partition(int x) {  // 不改变原来数据的顺序下，将所有小于x的结点排在其余结点之前
        ListNode beforeStart = null;  // 小于x的头节点
        ListNode beforeEnd = null;    // 小于x的尾节点
        ListNode afterStart = null;   // 大于x的头节点
        ListNode afterEnd = null;     // 大于x的尾节点
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                if(beforeStart == null){  // 第一次插入
                    beforeStart = beforeEnd = cur;
                }else{
                    beforeEnd.next = cur;
                    beforeEnd = beforeEnd.next;
                }
            }else{
                if(afterStart == null){
                    afterStart = afterEnd = cur;
                }else{
                    afterEnd.next = cur;
                    afterEnd = afterEnd.next;
                }
            }
            cur = cur.next;
        }
        // 如果没有小于x的节点
        if (beforeStart == null){
            return afterStart;
        }
        // 前后两部分衔接起来
        beforeEnd.next = afterStart;
        // 第2部分的最后一个节点的引用要置空，否则编译超出范围
        if(afterStart != null){
            afterEnd.next = null;
        }
        return beforeStart;
    }

3.7判断是否为回文链表。

提示

1、找到链表的中间节点；

2、将中间节点后面的节点反转；

3、头节点的值与最后一个节点的值进行比较，然后头节点往后，最后一个节点往前。

        注意此题需要区分链表的节点数，如果是奇数比较好判断，但如果是偶数，需要考虑另一个判断条件。

奇数情况下：

偶数情况下：

判断条件是 fast.next = slow;  不能是 slow.next = fast;

且该判断条件前提是两者的数据是相等的，因此判断顺序很重要。

    public boolean chkPalindrome(){ // 判断是否是回文链表
        if(head == null){
            return true;
        }
        // 1、找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
       javascript // 2、反转
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        // 3、判断是否是回文
        while(head != slow){
            if (head.val != slow.val){
                return false;
            }
            // 如果链表是偶数的话，应该是下面的判断条件
            // 前提是两个val值是相等的
            if (head.next == slow){  // 注意是head的下一个节点是slow才对，因为slow的下一个节点回到了slow后面了。
                return true;
            }
            head = head.next;
            slandroidow = slow.next;
        }
        return true;
    }

3.8输入两个链表，找出它们的公共节点。

    public SingleLinkedList.ListNode getIntersectionNode
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) {  // 两链表是否相交
        SingleLinkedList.ListNode pLong = headA;  // 假设链表A的长度比链表B的长
        SingleLinkedList.ListNode pShort = headB;
        int lenA = 0;   // 链表A的长度
        int lenB = 0;   // 链表B的长度
        while (pLong != null){
            lenA++;
            pLong = pLong.next;
        }
        while (pShort != null){
            lenB++;
            pShort = pShort.next;
        }
        // 因为在计算长度时改变了两个值，因此要从新定义
        pLong = headA;
        pShort = headB;
        // 计算两个链表长度的差值
        int len = lenA - lenB;
        if (len < 0){  // 如果len为负数，说明lenB大于lenA，规定pLong一定指向长的链表
            pLong = headB;
            pShort = headA;
            len = lenB - lenA;  // 记住要把差值换成正数
        }
        // 长的链表先走len步
        while (len != 0){
            pLong = pLong.next;
            len--;
        }
        // 两个引用同时走，知道它们相遇
        while (pLong != pShort){
            pLong = pLong.next;
            pShort = pShort.next;
        }
        if (pLong == null){
            return null;  // 说明没有相交
        }
        return pLong;
    }

测试：

    public static void creatIntersect
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB){  // 自己实现相交
        headA.next.next = headB.next.next.next;
    }
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(5);
        linkedList.addLast(1);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addFirst(4);
        linkedList2.addLast(1);
        linkedList2.addLast(6);
        linkedList2.addLast(8);
        linkedList2.addLast(4);
        linkedList2.addLast(5);
        creatIntersect(linkedList.head, linkedList2.head);
        SingleLinkedList.ListNode ret = getIntersectionNode(linkedList.head, linkedList2.head);
        System.out.println(ret.val);
    }

3.9判断链表中是否有环。* 进阶：给javascript定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

    public boolean hasCycle(){  // 判断当前链表是否有环
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
    public void creatLoop(){  // 创建环
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = head.next.next.next;
    }
    public ListNode detectCycle() {   // 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
        ListNode fast = head;
        ListNode slow = 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;  // 说明没有环
        }
        slow = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

测试类：

public class TestSingle {
    public static void main(String[] args) {
        // 测试返回链表开始入环的第一个节点。
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(5);
        linkedList.addLast(1);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
        linkedList.creatLoop();
        System.out.println(linkedList.hasCycle());
        SingleLinkedList.ListNode ret = linkedList.detectCycle();
        System.out.println(ret.val);
    }
}

到此这篇关于Java集合中的链表与结构详解的文章就介绍到这了,更多相关java集合链表内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！