链表的几种常见方法

妖狐艹你老母 2023-10-09 17:21 31阅读 0赞

--------------------

## 链表 ##

--------------------

> 提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

#### 文章目录 ####

*  链表
 *  前言
 *  一、创建链表
 *  二、打印链表
 *   *  1.递归打印
     *  2.遍历栈
     *  3.遍历链表
 *  三.查找链表中是否包含key
 *  四.单链表的长度
 *  五.头插法
 *  六.尾插法
 *  七.删除所有值为key的节点
 *  总结

--------------------

## 前言 ##

关于链表的一些基本实现

## 一、创建链表 ##

public class MySinglelist {
        
        class  ListNode{
        
            public int val;
            public ListNode next;
            public ListNode(int val){
        
                this.val = val;
            }
        }
        public ListNode head;
        public void creatlink(){
        
            ListNode listNode1 = new ListNode(12);
            ListNode listNode2 = new ListNode(45);
            ListNode listNode3 = new ListNode(23);
            ListNode listNode4 = new ListNode(90);
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            head = listNode1;
        }

## 二、打印链表 ##

### 1.递归打印 ###

public void display3(ListNode phead){
        
            if (phead == null){
        
                return;
            }
            if (phead.next == null){
        
                System.out.println(phead.val + "");
                return;
            }
            display3(phead.next);
            System.out.println(phead.val + "");
        }

### 2.遍历栈 ###

public void display4(){
        
            Stack<ListNode>stack = new Stack<>();
            ListNode cur = head;
            while (cur!=null){
        
                stack.push(cur);
                cur = cur.next;
            }
            while (!stack.isEmpty()) {
        
                ListNode top = stack.pop();
                System.out.print(top.val+" ");
            }
            System.out.println();
        }

\*\*

### 3.遍历链表 ###

public void display(){
        
            ListNode cur = head;
            while(cur!=null){
        
                System.out.println(cur.val + "");
                cur = cur.next;
            }
            System.out.println();
        }

\*\*

## 三.查找链表中是否包含key ##

public boolean contains(int key){
        
            ListNode cur = head;
            while(cur!=null){
        
                if (cur.val ==key){
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

## 四.单链表的长度 ##

public int size(){
        
            int count = 0;
            ListNode cur = head;
            while (cur!=null){
        
                count++;
                cur = cur.next;
            }
            return count;
        }

\*\*

## 五.头插法 ##

public void addFirst(int data){
        
            ListNode listNode = new ListNode(data);
            listNode.next = head;
            head = listNode;
        }

\*\*

## 六.尾插法 ##

public void addLast(int data){
        
            ListNode listNode = new ListNode(data);
            if (head == null){
        
                head = listNode;
                return;
            }
            ListNode cur = head;
            while (cur.next!=null){
        
                cur = cur.next;
            }
            cur.next = listNode;
        }

\*\*

## 七.删除所有值为key的节点 ##

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;
            }
        }
    }

## 总结 ##

好了，今天的就到这里了，欢迎大佬们补充和指正错误