【数据结构】单向链表的创建及4种应用

前言

相关传送门：===》【算法】链表手撕代码《===

链表的特点：

链表全称“链式存储结构”，属于线性表的一种；
链表由“数据域”和“指针域”这两部分组成；
在链表中，“实际存储”的是一个个“节点”，在物理上是非连续的数据结构；

链表的优点：

不需要提前预估长度，较于“数组”不存在“扩容操作”；
使用不连续的内存空间，实现灵活的内存动态管理；

链表的缺点：

较于数组会占用更多空间，因为其需要存放其他节点的指针；
不支持随机读取元素(RandomAccess) —— 数组类实现类一个标准类 RandomAccess表示支持随机读取；
遍历和查找元素较慢，适合读少写多的操作；

链表的时间复杂度：

插入和删除操作的复杂度为 O(1)；
查找或访问某一特定节点复杂度为 O(n)；

链表的分类：

单向链表
双向链表
循环链表
双向循环链表

自定义“单向”链表类

1. 自定义一个链表类，并完成“初始化链表”、“添加元素（头插法/尾插法）”、“计算链表长度”操作；

自定义链表

public class Linked{
    //定义头节点和尾节点
    private Node first,last;

    //链表长度
    private int size;

    //定义链表的节点
    static class Node{
        int val;  //数据域
        Node next; //后继元素(下一个元素)

        public Node(int x){
            this.val =x;
        }
    }
}

解读：

定义了私有成员变量 first 和 last ，分别代表链表的头节点和尾节点；
通过 size 变量记录链表的长度；
在自定义 Linked 类中定义一个静态内部类 Node ，用于表示链表的节点；
每个 Node 对象包含两个部分：int 类型的 val 变量用于存储节点的值，以及指向下一个节点的引用 next；

向链表中插入元素（头插法）

public class Linked{
    // 添加元素(头插法)
    public void addFirst(int val) {
    // 创建新节点
    final Node newNode = new Node(val);

    // 将新节点的 next 指向当前的第一个节点
    newNode.next = first;

    // 更新头节点为新节点
    first = newNode;

    // 如果链表为空，则更新尾节点为新节点
    if (last == null) {
        last = newNode;
    }

    // 增加链表长度
    size++;
    }

}

解读：

创建一个新节点 newNode，值为传入的参数 val；
将新节点的 next 指向当前的第一个节点 first ，把当前的头节点作为新节点的后继节点；
更新链表的头节点为新节点；
如果链表为空（即尾节点为 null ），则将尾节点也更新为新节点；
最后增加链表长度 size；

向链表中插入元素（尾插法）

public class Linked{
    //添加元素(尾插法)
    public void add(int val){
        //获取当前链表的尾节点
        final Node l = last ;

        //创建新节点
        final Node newNode = new Node(val);

        if(l !=null){
            //链表不为空
            l.next = newNode;
        }else{
            //链表为空
            first = newNode;
        }

        last = newNode;
        size++;
    }
}

解读：

获取当前链表的尾节点 last；
创建一个新的节点 newNode，值为传入的参数 val；
如果尾节点不为空，则将尾节点的 next 指向新节点；如果为空，则将头节点指向新节点；
更新尾节点为新节点，同时增加链表长度 size；

计算链表长度

public class Linked{
    //返回链表长度
    public int size(){
        return size;
    }
}

解读：

返回链表的长度，即 size 变量的值；

重写toString()方法

public class Linked{
      public String toString(){
        //使用线程不安全，但性能较好的StringBuilder
        StringBuilder ret = new StringBuilder();

        //遍历链表
        for(Node x =first;x !=null;x = x.next){
            ret.append(x.val);
            if(x.next !=null){
                ret.append("->");
            }
        }
        return ret.toString();
      }
}

解读：

使用 StringBuilder 构建字符串，遍历链表中的每个节点，将节点的值追加到字符串中；
如果节点有下一个节点，则在值之后添加"->"表示连接关系；
最后返回拼接好的字符串表示链表内容；

测试类

public class LinkedTest {
    public static void main(String[] args) {
        //初始化链表1
        Linked linked1 = new Linked();
        linked1.add(1);
        linked1.add(3);
        linked1.add(5);
        linked1.add(7);
        linked1.addFirst(9);
        System.out.println(linked1.size());
        System.out.println(linked1.toString());
    }
}

测试结果

对链表的应用

2. 在自定义链表类的基础上，使用“双指针”实现两个链表的合并；

    //双指针合并两个单向链表
    public static Linked meger(Linked l1 ,Linked l2 ){
        //定义双指针，分别执行两个有序链表的头节点
        Node p1 =l1.first, p2 = l2.first;

        //用于保存合并结果的链表
        Linked resultLinked = new Linked();

        while(p1 !=null || p2 !=null){

            if(p1 == null){
                resultLinked.add(p2.val);
                p2 = p2.next;
                continue;
            }

            if(p2 == null){
                resultLinked.add(p1.val);
                p1 = p1.next;
                continue;
            }

            //比较两个节点
            if(p1.val < p2.val){
                resultLinked.add(p1.val);
                p1 = p1.next;
            }else{
                resultLinked.add(p2.val);
                p2 = p2.next;
            }
        }
        return resultLinked;
    }

解读：

接收两个参数 l1 和 l2，分别表示要合并的两个链表；
在方法内部定义两个指针 p1 和 p2，分别指向两个链表的头节点；
定义一个 Linked 对象 resultLinked 用于保存合并结果；
进入循环后会判断两个指针是否都指向 null，只要其中一个指针不为空就继续执行；
如果 p1 或 p2 任一个为 null，则直接将另一个链表剩余部分添加到 resultLinked 中，并移动指针到下一个节点；
如果两个节点都不为 null，则比较两个节点的值：如果 p1 的值小于 p2 的值，则将 p1 的值添加到 resultLinked 中，并将 p1 指针指向下一个节点；
如果 p2 的值小于等于 p1 的值，则将 p2 的值添加到 resultLinked 中，并将 p2 指针指向下一个节点；
循环结束后，返回合并后的链表 resultLinked；

时间复杂度为 O(m+n)，其中 m 和 n 分别表示两个链表的长度；

测试用例

        Linked linked2 =new Linked();
        linked2.add(2);
        linked2.add(4);
        linked2.add(6);
        linked2.add(8);
        linked2.add(10);
        //链表合并
        Linked megerRet = Linked.meger(linked1, linked2);
        System.out.println("合并结果"+megerRet);

测试结果

3. 在自定义链表类的基础上，通过“栈”反转链表；

    public static Linked reverseLinked(Linked linked){
        Stack<Node> nodeStack = new Stack<>();

        //遍历链表，将所有Node节点，存入栈中
        Node currentNode = linked.first;
        if(currentNode ==null){
            return linked;
        }

        while (currentNode !=null){
            nodeStack.push(currentNode);
            currentNode =currentNode.next;
        }

        //遍历栈，将栈中的Node节点，从栈顶依次出栈(逆序)，并存入链表中
        linked = new Linked(); //清空原链表
        while (!nodeStack.empty()){
            linked.add(nodeStack.pop().val);
        }
        return linked;
    }

解读：

接收一个参数 linked，表示要逆序的链表；
创建一个 Stack 对象 nodeStack 用于存储链表的节点；
获取链表的头节点，并将其赋值给 currentNode；
如果链表为空，直接返回原链表，否则，通过循环遍历链表，将每个节点依次压入栈中，并将 currentNode 指针移动到下一个节点；
创建一个新的空链表对象 linked，用于存放逆序后的节点；
通过循环遍历栈中的节点，每次从栈顶取出一个节点，并将其值添加到 linked 链表中（此时节点的顺序已经逆序）；
循环结束后，返回逆序后的链表 linked；

时间复杂度为 O(n)，其中 n 表示链表的长度；

测试用例

        Linked linked1 = new Linked();
        linked1.add(1);
        linked1.add(3);
        linked1.add(5);
        linked1.add(7);
        linked1.add(9);
        linked1 = Linked.reverseLinked(linked1);
        System.out.println("链表反转的结果"+linked1);

测试结果

4. 在自定义链表类的基础上，计算两个大型整数(BigInteger)和；

    //用"链表"计算两个大型整数和
    public static Linked addTwoNumber(Linked l1 ,Linked l2){
        //从个位开始计算(链表的头部)
        Node n1 =l1.first;
        Node n2 =l2.first;

        Linked retLinked = new Linked();

        int carry = 0;//进位

        while ( n1 != null || n2 !=null){
            //分别获取当前计算的数字
            int x =n1 != null ? n1.val :0;
            int y =n2 != null ? n2.val :0;

            int sum =x + y + carry;

            //计算进位值
            carry = sum /10;

            //保存当前位计算结果
            retLinked.add(sum %10);

            if(n1 !=null){
                n1 =n1.next;
            }

            if(n2 !=null){
                n2 =n2.next;
            }
        }

        if(carry !=0){
            retLinked.add(carry);
        }

        retLinked= Linked.reverseLinked(retLinked);
        return retLinked;
    }

解读：

接收两个参数 l1 和 l2，分别表示要相加的两个链表；
n1 和 n2 分别表示链表 l1 和 l2 的头节点；
通过将 l1 和 l2 的头节点赋值给 n1 和 n2，开始从个位开始计算两个链表的和；
创建一个 Linked 对象 retLinked，用于存储计算结果；
carry 表示进位的值，初始值为 0；
通过循环遍历链表中的节点，直到两个链表都遍历完；
在循环中，首先判断当前节点是否为空，如果不为空，则获取当前节点的值；如果为空，则将当前节点的值置为 0；
计算当前位的和（包括进位），并更新进位的值；
将当前位的和除以 10 取余数，并将余数添加到 retLinked 链表中作为当前位的计算结果；
如果链表节点不为空，则将当前节点指针移动到下一个节点；
在循环结束后，如果进位不为 0，则将进位值添加到 retLinked 链表的末尾；
最后，调用 Linked 类的静态方法 reverseLinked 将 retLinked 链表进行逆序操作；
返回逆序后的链表 retLinked，即两个大型整数(BigInteger)的和；

从个位开始逐位计算两个大型整数的和，并将结果保存在一个新的链表中。时间复杂度为 O(max(n, m))，其中 n 和 m 分别表示链表 l1 和 l2 的长度；

测试用例

        Linked linked3 = new Linked();
        linked3.add(3);
        linked3.add(4);
        linked3.add(2);
        Linked linked4 =new Linked();
        linked4.add(1);
        linked4.add(2);
        linked4.add(3);
        Linked linked = Linked.addTwoNumber(linked3, linked4);
        linked3 =Linked.reverseLinked(linked3);
        linked4 =Linked.reverseLinked(linked4);
        System.out.printf("两数字%s,%s计算和:%s\n",linked3.toString(),linked4.toString(),linked.toString2());

测试结果

5.1 在自定义链表类的基础上，使用"Set"集合测试链表中是否存在环路现象；

   public static boolean hasCycle1(Node node){
        HashSet<Node> nodeHashSet = new HashSet<>();

        while (node !=null){
            if(nodeHashSet.contains(node)){
                return true;
            }

            nodeHashSet.add(node); //保存至Set
            node = node.next;
        }

        return false;
    }

解读：

接收一个参数 node，表示链表的头节点；
创建一个 HashSet 对象 nodeHashSet，用于存储遍历过的节点；
通过循环遍历链表中的节点，直到遍历到链表末尾（node 为 null）或发现循环；
在循环中，首先检查当前节点是否已经存在于 nodeHashSet 中，如果存在则说明链表中存在循环，直接返回 true；
如果当前节点不在 nodeHashSet 中，则将当前节点添加到 nodeHashSet 中，并将指针移动到下一个节点；
如果遍历完整个链表后都没有发现循环，则返回 false，表示链表中不存在循环；

时间复杂度为 O(n)，其中 n 表示链表中节点的数量；

测试用例

        //判断链表中是否存在环路
        Linked.Node node1 =new Linked.Node(1);
        Linked.Node node2 =new Linked.Node(2);
        Linked.Node node3 =new Linked.Node(3);
        Linked.Node node4 =new Linked.Node(4);
        Linked.Node node5 =new Linked.Node(5);


        node1.next =node2;
        node2.next =node3;
        node3.next =node4;
        node4.next =node5;
        for(Linked.Node x =node1;x!=null;x =x.next){
            System.out.print(x.val);

            if(x.next !=null) {
                System.out.print("=>");
            }
        }
        System.out.println("是否存在环路:"+Linked.hasCycle1(node1));

测试结果

5.2 在自定义链表类的基础上，基于"快慢指针"判断链表中是否存在环路；

   public static  boolean hasCycle2(Node head){
        //定义快慢指针
        Node fast = head;
        Node slow = head;

        while (fast != null && fast.next != null && slow !=null){
            fast =fast.next.next; //快指针每次移动2步
            slow =slow.next; //慢指针每次移动1步

            if(fast == slow){
                return true;
            }
        }
        return false; //链表无环
    }

解读：

接收一个参数 head，表示链表的头节点；
定义两个指针 fast 和 slow，初始时它们都指向链表的头节点 head；
通过循环遍历链表中的节点，直到快指针移动到链表末尾（fast 或 fast.next 为 null）；
在循环中，快指针每次向前移动两步（fast = fast.next.next），慢指针每次向前移动一步（slow = slow.next）；
在每次移动后，判断快指针是否与慢指针相遇，如果相遇则说明链表中存在循环，直接返回 true；
如果遍历完整个链表后快指针到达链表末尾仍未相遇，则返回 false，表示链表中不存在循环；

时间复杂度为 O(n)，其中 n 表示链表中节点的数量。这种方法在空间复杂度上优于使用 HashSet 存储节点的方法；

测试用例

        //判断链表中是否存在环路
        Linked.Node node1 =new Linked.Node(1);
        Linked.Node node2 =new Linked.Node(2);
        Linked.Node node3 =new Linked.Node(3);
        Linked.Node node4 =new Linked.Node(4);
        Linked.Node node5 =new Linked.Node(5);


        node1.next =node2;
        node2.next =node3;
        node3.next =node4;
        node4.next =node5;
        node5.next =node3; //存在环路

        System.out.println("是否存在环路:"+Linked.hasCycle2(node2));