• 【数据结构与算法】链表的实现以及相关算法

    目录

    双链表的实现

    单链表的实现

    有序列表的合并（双指针法）

    链表的反转 

    链表实现两数之和 

    判定链表是否有环

    判断链表是否相交

    单链表的排序

    双链表的实现

    1. public class DLinkedList {
    2.     private Node first;
    3.     private Node last;
    4.     int size;
    5.  
    6.     /**
    7.      * 头插法
    8.      * @param item
    9.      */
    10.     public void addFirst(E item){
    11.         Node f =first;
    12.  
    13.         Node newNode =new Node(null,item,f);
    14.  
    15.         first =newNode;
    16.  
    17.         if (f==null){
    18.             last =newNode;
    19.         }else {
    20.             f.prev=newNode;
    21.         }
    22.         size++;
    23.     }
    24.  
    25.     /**
    26.      * 尾插法
    27.      * @param item
    28.      */
    29.     public void addLast(E item){
    30.         Node l =last;
    31.  
    32.         Node newNode =new Node(l,item,null);
    33.  
    34.         last =newNode;
    35.  
    36.         if (l==null){
    37.             first=newNode;
    38.         }else {
    39.             l.next=newNode;
    40.         }
    41.         size++;
    42.     }
    43.  
    44.     /**
    45.      * 删除头节点
    46.      */
    47.     public void deleteFirst(){
    48.         Node f =first;
    49.         Node n =first.next;
    50.  
    51.         f.next =null;
    52.         f.item=null;
    53.  
    54.         first=n;
    55.  
    56.         if (n==null){
    57.             last=null;
    58.         }else {
    59.             n.prev=null;
    60.         }
    61.  
    62.         size--;
    63.     }
    64.  
    65.     /**
    66.      * 删除尾节点
    67.      */
    68.     public void deleteLast(){
    69.         Node l =last;
    70.         Node p =last.prev;
    71.  
    72.         l.item=null;
    73.         l.prev=null;
    74.  
    75.         last=p;
    76.  
    77.         if (p==null){
    78.             first=null;
    79.         }else {
    80.             p.next=null;
    81.         }
    82.  
    83.         size--;
    84.     }
    85.  
    86.     /**
    87.      * 从头开始遍历
    88.      * @return
    89.      */
    90.     public String toStringForFirst() {
    91.         StringJoiner sj =new StringJoiner("->");
    92.         for (Node n= first;n!=null;n =n.next){
    93.             sj.add(n.item.toString());
    94.         }
    95.         return sj.toString();
    96.     }
    97.  
    98.     /**
    99.      * 从尾开始遍历
    100.      * @return
    101.      */
    102.     public String toStringForLast(){
    103.         StringJoiner sj =new StringJoiner("<-");
    104.         for (Node n =last;n!=null;n=n.prev){
    105.             sj.add(n.item.toString());
    106.         }
    107.         return sj.toString();
    108.     }
    109.  
    110.     @Override
    111.     public String toString() {
    112.         StringJoiner sj =new StringJoiner("<->");
    113.         for (Node n= first;n!=null;n =n.next){
    114.             sj.add(n.item.toString());
    115.         }
    116.         return sj.toString();
    117.     }
    118.  
    119.     /**
    120.      * 节点内部类
    121.      * @param 
    122.      */
    123.     static class Node{
    124.         private E item;
    125.         private Node prev;
    126.         private Node next;
    127.  
    128.         Node(Node prev,E item,Node next){
    129.             this.prev=prev;
    130.             this.item=item;
    131.             this.next=next;
    132.         }
    133.     }
    134. }

    单链表的实现

    1. public class LinkedList1 {
    2.     //头节点
    3.     Node first;
    4.     //尾节点
    5.     Node last;
    6.     //大小
    7.     int size = 0;
    8.  
    9.     //头插法
    10.     public void addFirst(int v) {
    11.         Node newNode = new Node(v);
    12.  
    13.         Node f = first;
    14.  
    15.         first = newNode;
    16.  
    17.         if (f == null) {
    18.             last = newNode;
    19.         } else {
    20.             newNode.next = f;
    21.         }
    22.         size++;
    23.     }
    24.  
    25.     //尾插法
    26.     public void addLast(int v) {
    27.         Node newNode = new Node(v);
    28.  
    29.         Node l = last;
    30.  
    31.         last = newNode;
    32.  
    33.         if (l == null) {
    34.             first = newNode;
    35.         } else {
    36.             l.next = newNode;
    37.         }
    38.         size++;
    39.     }
    40.  
    41.     //使用节点尾插
    42.     public void addNode(Node node){
    43.         if (last ==null){
    44.             last=node;
    45.             first=node;
    46.         }else {
    47.             Node l =last;
    48.             l.next=node;
    49.             last=node;
    50.         }
    51.  
    52.     }
    53.  
    54.  
    55.     //链表的遍历
    56.     @Override
    57.     public String toString() {
    58.         StringJoiner sj = new StringJoiner("->");
    59.         for (Node n = first; n != null; n = n.next) {
    60.             sj.add(String.valueOf(n.val));
    61.         }
    62.         return sj.toString();
    63.     }
    64.  
    65.  
    66.  
    67.     public static class Node {
    68.         int val;
    69.         Node next;
    70.  
    71.         Node(int val) {
    72.             this.val = val;
    73.         }
    74.     }
    75. }

    以下所有算法都是基于上面单链表的实现方法

    有序列表的合并（双指针法）

    1. //链表的有序合并排序
    2.     public static LinkedList1 merge(LinkedList1 list1, LinkedList1 list2) {
    3.         Node n1 = list1.first, n2 = list2.first;
    4.         LinkedList1 result = new LinkedList1();
    5.         while (n1 != null || n2 != null) {
    6.             if (n1 == null) {
    7.                 result.addLast(n2.val);
    8.                 n2 = n2.next;
    9.                 continue;
    10.             }
    11.             if (n2 == null) {
    12.                 result.addLast(n1.val);
    13.                 n1 = n1.next;
    14.                 continue;
    15.             }
    16.  
    17.             if (n1.val < n2.val) {
    18.                 result.addLast(n1.val);
    19.                 n1 = n1.next;
    20.             } else {
    21.                 result.addLast(n2.val);
    22.                 n2 = n2.next;
    23.  
    24.             }
    25.         }
    26.         return result;
    27.     }

     测试

    1. LinkedList1 linkedList1 =new LinkedList1();
    2.         linkedList1.addLast(1);
    3.         linkedList1.addLast(4);
    4.         linkedList1.addLast(6);
    5.  
    6.  
    7.         LinkedList1 linkedList2 =new LinkedList1();
    8.         linkedList2.addLast(2);
    9.         linkedList2.addLast(3);
    10.         linkedList2.addLast(5);
    11.         linkedList2.addLast(9);
    12.  
    13.         System.out.println("链表1："+linkedList1);
    14.         System.out.println("链表2："+linkedList2);
    15.         //有序链表的合并排序
    16.         System.out.println("链表1与链表2合并："+LinkedList1.merge(linkedList1, linkedList2));

    链表的反转 

    1. //链表的反转
    2.     public static LinkedList1 reverseLinked(LinkedList1 list1) {
    3.         Stack stack = new Stack<>();
    4.         for (Node n = list1.first; n != null; n = n.next) {
    5.             stack.add(n);
    6.         }
    7.         LinkedList1 result = new LinkedList1();
    8.         while (!stack.isEmpty()) {
    9.             result.addLast(stack.pop().val);
    10.         }
    11.         return result;
    12.     }

    测试

    1.         LinkedList1 linkedList1 =new LinkedList1();
    2.         linkedList1.addLast(1);
    3.         linkedList1.addLast(4);
    4.         linkedList1.addLast(6);
    5.  
    6.         System.out.println("链表1："+linkedList1);
    7.         //链表的反转
    8.         System.out.println("链表1反转后："+LinkedList1.reverseLinked(linkedList1));

    测试结果

    链表实现两数之和 

    1.     //两数之和
    2.     public static LinkedList1 addNumber(LinkedList1 list1, LinkedList1 list2) {
    3.         Node n1 = list1.first, n2 = list2.first;
    4.         LinkedList1 result = new LinkedList1();
    5.         int carry = 0;
    6.         while (n1 != null || n2 != null) {
    7.             int x = n1 != null ? n1.val : 0;
    8.             int y = n2 != null ? n2.val : 0;
    9.             int sum = x + y + carry;
    10.             carry = sum / 10;
    11.             result.addLast(sum % 10);
    12.  
    13.             if (n1 != null) {
    14.                 n1 = n1.next;
    15.             }
    16.             if (n2 != null) {
    17.                 n2 = n2.next;
    18.             }
    19.         }
    20.         if (carry != 0) {
    21.             result.addLast(carry);
    22.         }
    23.         return result;
    24.     }

    测试

    1.         LinkedList1 linkedList1 =new LinkedList1();
    2.         linkedList1.addLast(1);
    3.         linkedList1.addLast(4);
    4.         linkedList1.addLast(6);
    5.  
    6.  
    7.         LinkedList1 linkedList2 =new LinkedList1();
    8.         linkedList2.addLast(2);
    9.         linkedList2.addLast(3);
    10.         linkedList2.addLast(5);
    11.         linkedList2.addLast(9);
    12.         //两数之和
    13.         System.out.println("链表1："+linkedList1);
    14.         System.out.println("链表2："+linkedList2);
    15.         System.out.println("链表1+链表2："+LinkedList1.addNumber(linkedList1,linkedList2));

    测试结果（注意从左到右依次是个十百位）

    判定链表是否有环

    方法一 通过set集合

    1.     //set集合判断是否有环
    2.     public static boolean hasCycle(Node node) {
    3.         Set set = new HashSet<>();
    4.  
    5.         while (node != null) {
    6.             if (set.contains(node)) {
    7.                 return true;
    8.             }
    9.             set.add(node);
    10.  
    11.             node = node.next;
    12.         }
    13.         return false;
    14.     }

    方法二 通过快慢指针

    1.     //快慢指针判断是否有环
    2.     public static boolean hasCycle2(Node node) {
    3.         Node fast = node;//快指针
    4.         Node slow = node;//慢指针
    5.  
    6.         //判断是不是空节点
    7.         if (node == null) {
    8.             return false;
    9.         }
    10.         while (fast != null && fast.next != null && slow != null) {
    11.             fast = fast.next.next;
    12.             slow = slow.next;
    13.  
    14.             if (fast == slow) {
    15.                 return true;
    16.             }
    17.         }
    18.         return false;
    19.     }

    测试 无论方法一还是二 测试结果都是相同 一般使用方法二 效率更高 更节省资源

    1.         LinkedList1.Node node1 =new LinkedList1.Node(1);
    2.         LinkedList1.Node node2 =new LinkedList1.Node(2);
    3.         LinkedList1.Node node3 =new LinkedList1.Node(3);
    4.         LinkedList1.Node node4 =new LinkedList1.Node(4);
    5.         LinkedList1.Node node5 =new LinkedList1.Node(5);
    6.  
    7.         node1.next=node2;
    8.         node2.next=node3;
    9.         node3.next=node4;
    10.         node4.next=node5;
    11.         node5.next=node3;//环 注意这是专门设置的环
    12.  
    13.  
    14.         //set集合判断是否有环
    15.         System.out.println("set集合判断是否有环:"+LinkedList1.hasCycle(node1));
    16.         //快慢指针判断是否有环
    17.         System.out.println("快慢指针判断是否有环:"+LinkedList1.hasCycle2(node1));

    测试结果

    判断链表是否相交

    方法一  双重循环暴力解决两条链表是否相交

    1. //双重循环暴力解决两条链表是否相交
    2.     public static boolean isCross(LinkedList1 list1,LinkedList1 list2){
    3.         for (Node n1 =list1.first;n1!=null;n1=n1.next){
    4.             for (Node n2 =list2.first;n2!=null;n2=n2.next){
    5.                 if (n1==n2){
    6.                     return true;
    7.                 }
    8.             }
    9.         }
    10.         return false;
    11.     }

    方法二 双指针判断链表是否相交

    1. //双指针判断链表是否相交
    2. public static boolean isCross2(LinkedList1 list1,LinkedList1 list2){
    3.         if (list1 ==null ||list2==null){
    4.             return false;
    5.         }
    6.  
    7.         Node p =list1.size()>list2.size()?list1.first:list2.first;
    8.         Node q =list1.size()>list2.size()?list2.first:list1.first;
    9.  
    10.         int diff =Math.abs(list1.size()-list2.size());
    11.  
    12.         while (diff-- >0){
    13.             p=p.next;
    14.         }
    15.  
    16.         while (p!=q){
    17.             p=p.next;
    18.             q=q.next;
    19.         }
    20.  
    21.         if (p!=null){
    22.             return true;
    23.         }else {
    24.             return false;
    25.         }
    26.     }

    测试

    1.         LinkedList1.Node node1 =new LinkedList1.Node(1);
    2.         LinkedList1.Node node2 =new LinkedList1.Node(2);
    3.         LinkedList1.Node node3 =new LinkedList1.Node(3);
    4.         LinkedList1.Node node4 =new LinkedList1.Node(4);
    5.         LinkedList1.Node node5 =new LinkedList1.Node(5);
    6.  
    7.         LinkedList1.Node nodeA =new LinkedList1.Node('A');
    8.         LinkedList1.Node nodeB =new LinkedList1.Node('B');
    9.         LinkedList1.Node nodeC =new LinkedList1.Node('C');
    10.  
    11.         LinkedList1 linkedList1 =new LinkedList1();
    12.         linkedList1.addNode(node1);
    13.         linkedList1.addNode(node2);
    14.         linkedList1.addNode(node3);
    15.         linkedList1.addNode(node4);
    16.         linkedList1.addNode(node5);
    17.  
    18.         LinkedList1 linkedList2 =new LinkedList1();
    19.         linkedList2.addNode(nodeA);
    20.         linkedList2.addNode(nodeB);
    21.         linkedList2.addNode(nodeC);
    22.         linkedList2.addNode(node3);
    23.  
    24.         System.out.println(linkedList1);
    25.         System.out.println(linkedList2);
    26.  
    27.  
    28.         System.out.println(LinkedList1.isCross(linkedList1,linkedList2));
    29.         System.out.println(LinkedList1.isCross2(linkedList1,linkedList2));

    测试结果

    单链表的排序

    链表的排序与数组是一样的这里使用冒泡排序

    1.      /**
    2.      * 冒泡排序
    3.      * @param first 头节点
    4.      */
    5.     public void sortInList(Node first){
    6.         if (first ==null||first.next==null){
    7.             return ;
    8.         }
    9.         Node p,q;
    10.         for (p=first;p!=null;p=p.next){
    11.             for (q=p.next;q!=null;q=q.next){
    12.                 if (p.val>q.val){
    13.                     int temp =p.val;
    14.                     p.val=q.val;
    15.                     q.val=temp;
    16.                 }
    17.             }
    18.         }
    19.     }

    测试

    1.         LinkedList1 linkedList2 = new LinkedList1();
    2.         linkedList2.addLast(5);
    3.         linkedList2.addLast(3);
    4.         linkedList2.addLast(2);
    5.         linkedList2.addLast(9);
    6.         System.out.println(linkedList2);
    7.         linkedList2.sortInList(linkedList2.first);
    8.         System.out.println(linkedList2);

    测试结果

  • 相关阅读:
    学生HTML个人网页作业作品 简单的IT技术个人简历模板html下载 简单个人网页设计作业 静态HTML个人博客主页
    java 多线程乐观锁与悲观锁
    【Leetcode刷题】二分查找
    VS Code | 在VS Code中搭建你的R语言运行环境吧！~（图文介绍超详细）
    【Prism系列】Prism中的命令
    FFmpeg开发笔记（一）搭建Linux系统的开发环境
    【LeetCode】插入区间
    探究Nginx应用场景
    使用显著性检测的可见光和红外图像的两尺度图像融合（Matlab代码实现）
    机器学习中的集成学习算法和K-近邻算法及其优缺点
  • 原文地址：https://blog.csdn.net/c1390527393/article/details/133325729