一起学算法（链表篇）

不念不忘少年蓝@ 2023-10-14 11:18 83阅读 0赞

### 1.链表的概念 ###

对于顺序存储的结构最大的缺点就是插入和排序的时候需要移动大量的元素，所以链表的出生由此而来

**先上代码**：

// 链表
    public class LinkedList<T extends Comparable> {
        // 结点类
        class Node {
            T ele; // 当前结点上的元素内容
            Node next; // 指向下个结点的索引
    
            public Node(T ele) {
                this.ele = ele;
            }
    
            @Override
            public String toString() {
                return ele.toString();
            }
        }
    
        // 头结点
        private Node head;
    
        // 链表中实际存放结点的个数
        private int size;
    
        // 判断链表是否为空
        public boolean isEmpty() {
            return head == null;
        }
    
        // 获取链表中结点的个数
        public int getSize() {
            return this.size;
        }
    
        public void addHead(T ele) {
            this.add(0, ele);
        }
    
        public void addTail(T ele) {
            this.add(this.size, ele);
        }
    
        // 在指定位置添加结点, 关键点: 找到待插入位置的前一个结点
        public void add(int index, T ele) {
            if (index < 0 || index > this.size) {
                throw new IllegalArgumentException("index is invalid!");
            }
            Node node = new Node(ele);
    
            // 给链表增加一个虚拟头结点, 解决在链表的头部添加时的特殊处理
            Node dummyHead = new Node(null);
            dummyHead.next = head;
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            node.next = prev.next;
            prev.next = node;
            // 更新头结点
            head = dummyHead.next;
            this.size++;
        }
          //根据索引找对应的元素
        public T get(int index){
            if(index<0||index>=this.size){
                return null;
            }
            Node cur=head;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            return cur.ele;
        }
    //获取头节点的元素
        public T getFirst(){
           return get(0);
        }
        //获取尾结点的元素
        public T getLast(){
            return get(this.size-1);
        }
       //判断是否包含该元素
        public boolean contain(T ele){
            Node cur=head;
            for (int i = 0; i < this.size; i++) {
               if(cur.ele.compareTo(ele)==0){
                   return true;
               }
                 cur=cur.next;
            }
            return false;
        }
        //将链表中的某个元素进行替换
        public void set(T ele,int index) {
            if(index<0||index>=this.size){
            }
            Node cur=head;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            cur.ele=ele;
        }
        //将链表中的元素进行删除
        public void delete(int index) {
            if (index < 0 || index >= this.size) {
    
            }
            //无虚拟头结点
    //        if (index == 0) {
    //            Node delnode = head;
    //            head = delnode.next;
    //            delnode.next = null;
    //            this.size--;
    //        } else {
    //            Node pre = head;
    //            Node cur = pre.next;
    //            for (int i = 1; i < index; i++) {
    //                pre = pre.next;
    //                cur=cur.next;
    //            }
    //            Node delnode =cur;
    //            pre.next = delnode.next;
    //            delnode.next = null;
    //            this.size--;
    //            cur = cur.next;
    
                //有虚拟头节点
            Node dummyNode=new Node(null);
            dummyNode.next=head;
            Node pre=dummyNode;
            Node cur=pre.next;
            for (int i = 0; i < index; i++) {
                pre=pre.next;
                cur=cur.next;
            }
            Node delnode =cur;
                pre.next = delnode.next;
                delnode.next = null;
                this.size--;
                cur = cur.next;
            }
    
        @Override
        public String toString() {
            //IO流
            StringBuilder sb = new StringBuilder();
            // 头结点不能动
            Node cur = head;
            while (cur != null) {
                sb.append(cur + "-->");
                cur = cur.next;
            }
            return sb.toString();
        }
    }

#### 1.链表的定义 ####

链表是由一个个结点组成的，每个结点之间通过链接关系串联起来的，每个结点都有一个前驱、一个后继，最后一个结点的后继结点为空节点

![3a7163f8f24b01035ea7969c12640c4a.png][]

由链接关系A->B组织起来的两个结点，B称为A的后继结点，A被称为B的前驱结点，链表分为单向链表、双向链表、循环链表等

#### 2.链表结点的定义 ####

由于该类继承了Comparable,所以该类中的元素具有了比较性，ele代表的是数据域，可以是任意的类型，由编码的人自行指定，next代表指针域，指向后继结点的地址

![aba60a5d09c616dd77a38e8115110003.png][]

#### 3.虚拟头结点 ####

为了方便对链表的头结点执行操作，往往会建立一个虚拟头结点，这个结点上也不存储数据，也就是ele字段永远为空，或者是为一个特殊的标识

![b5062f7f90e544db9377a4c7bf6e2a43.png][]

ListNode dummyNode=new ListNode(head,-1);//后继结点为头结点，默认值为-1

### 2.链表的遍历 ###

#### 1.遍历的含义 ####

遍历就是从链表头结点开始，对所有的结点一次访问的过程

#### 2.动画演示 ####

![5f66a939ab68407a2d5988fb01ff98b7.gif][]

虚拟头节点head用-1进行标识，tmp代表当前遍历到的结点，其中tmp后的数字代表链表结点的索引

### 3.链表结点的索引 ###

#### 1.索引的含义 ####

链表结点的索引就是给定一个链表头和一个下标index,通过下标获取到链表第index个元素

#### 2.动画演示 ####

![8dc5f45b2b33c6054ce3e9e19544904e.gif][]

#### 3.代码演示 ####

//根据索引找对应的元素
        public T get(int index){
            if(index<0||index>=this.size){
                return null;
            }
            Node cur=head;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            return cur.ele;
        }

### 4.链表结点的插入 ###

#### 1.插入的含义 ####

给定一个链表头和一个位置index(index>=0)和一个值ele生成一个值为ele的结点，并且将它插入到链表第index之后的位置

#### 2.动画演示 ####

![64f36f08498b59ce5f8080d7fb3e26ef.gif][]

#### 3.演示代码 ####

// 在指定位置添加结点, 关键点: 找到待插入位置的前一个结点
        public void add(int index, T ele) {
            if (index < 0 || index > this.size) {
                throw new IllegalArgumentException("index is invalid!");
            }
            Node node = new Node(ele);
    
            // 给链表增加一个虚拟头结点, 解决在链表的头部添加时的特殊处理
            Node dummyHead = new Node(null);
            dummyHead.next = head;
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            node.next = prev.next;
            prev.next = node;
            // 更新头结点
            head = dummyHead.next;
            this.size++;
        }

### 5.链表结点的删除 ###

#### 1.删除的含义 ####

给定一个链表头和一个位置index(index>=1)将位置index的结点删除，并且返回被删除的结点，由于第一个结点是虚拟头结点，所以我们要从索引为1的位置开始

#### 2.动画演示 ####

![ee948a770629324481d03910224129c2.gif][]

#### 3.代码演示 ####

//将链表中的元素进行删除
        public void delete(int index) {
            if (index < 0 || index >= this.size) {
    
            }
            //无虚拟头结点
    //        if (index == 0) {
    //            Node delnode = head;
    //            head = delnode.next;
    //            delnode.next = null;
    //            this.size--;
    //        } else {
    //            Node pre = head;
    //            Node cur = pre.next;
    //            for (int i = 1; i < index; i++) {
    //                pre = pre.next;
    //                cur=cur.next;
    //            }
    //            Node delnode =cur;
    //            pre.next = delnode.next;
    //            delnode.next = null;
    //            this.size--;
    //            cur = cur.next;
    
                //有虚拟头节点
            Node dummyNode=new Node(null);
            dummyNode.next=head;
            Node pre=dummyNode;
            Node cur=pre.next;
            for (int i = 0; i < index; i++) {
                pre=pre.next;
                cur=cur.next;
            }
            Node delnode =cur;
                pre.next = delnode.next;
                delnode.next = null;
                this.size--;
                cur = cur.next;
            }

### 6.链表结点的查找 ###

#### 1.查找的含义 ####

查找的含义就是给定一个值通过遍历链表找到链表值和给定相等的那个结点

#### 2.动画演示 ####

![8dc5f45b2b33c6054ce3e9e19544904e.gif][]

#### 3.代码演示 ####

### 7.链表结点的修改 ###

#### 1.修改的含义 ####

给定一个链表头一个位置index(index>=1)和一个值ele，将位置index的结点值修改为ele

#### 2.代码演示 ####

//将链表中的某个元素进行替换
        public void set(T ele,int index) {
            if(index<0||index>=this.size){
            }
            Node cur=head;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            cur.ele=ele;
        }

### leetcode题单： ###

[返回倒数第k个节点][k]

// 双指针
        public int kthToLast(ListNode head, int k) {
            ListNode fast = head;
            ListNode slow = head;
            // 让快指针先走k步
            for (int i = 0 ; i < k ; i++) {
                fast = fast.next;
            }
            // 再让快指针和慢指针同时移动
            // 当快指针走到链表结尾时
            // 慢指针所指向的节点就是目标节点
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow.val;
        }

[删除链表的倒数第N个节点][N]

//利用双指针
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if(head==null||n<0){
               return head;
           }
           ListNode dummyNode=new ListNode(0,head);
           ListNode slow=dummyNode;
           ListNode fast=dummyNode;
            for (int i = 0; i <n+1; i++) {
                fast=fast.next;
            }
            while(fast!=null){
                slow=slow.next;
                fast=fast.next;
            }
            slow.next=slow.next.next;
            return dummyNode.next;
        }

[反转链表][Link 1]

public ListNode reverseList(ListNode head) {
           if(head==null||head.next==null){
               return head;
           }
           ListNode resNode=reverseList(head.next);
           head.next.next=head;
           head.next=null;
           return resNode;
        }
    
    
         public ListNode reverseList(ListNode head) {
            //如果头结点为空或者是头结点的后继节点为空的话，直接返回头结点
                 if(head==null ||head.next==null){
                     return head;
                 }
            //定义指针
            ListNode cur=head;
            ListNode temp=cur.next;
            ListNode pre=null;
            while(cur!=null){
                temp=cur.next;
                cur.next=pre;
                pre=cur;
                cur=temp;
            }
            return pre;
        }

[删除链表中的节点][Link 2]

public void deleteNode(ListNode node) {
            node.val=node.next.val;
            node.next=node.next.next;
        }

[两两交换链表中的节点][Link 3]

//方法一
     public ListNode swapPairs(ListNode head) {
            if(head==null||head.next==null){
                return head;
            }
            ListNode left=head;
            ListNode right=left.next;
            ListNode newNode=swapPairs(right.next);
            left.next=newNode;
            right.next=left;
            return right;
        }
        //方法二
        public ListNode swapPairs(ListNode head) {
           if(head==null||head.next==null){
              return head;
          }
          ListNode r=head;
            for (int i = 0; i <2; i++) {
                if(r==null){
                    return head;
                }
                r=r.next;
            }
            ListNode node=reverse(head,r);
            head.next=swapPairs(r);
            return node;
        }
       
        public ListNode reverse(ListNode head,ListNode right){
            ListNode pre=null,curNode=head,next=null;
            while(curNode!=right){
                next=curNode.next;
                curNode.next=pre;
                pre=curNode;
                curNode=next;
            }
            return pre;
    }
    
       //方法三
       public ListNode swapPairs(ListNode head) {
            //对入参进行判断
            if(head==null||head.next==null){
                 return head;
               }
               ListNode dummyHead=new ListNode(Integer.MIN_VALUE);
               dummyHead.next=head;
               ListNode pre=dummyHead;
               ListNode cur=pre.next;
               ListNode next=cur.next;
              
          while(cur!=null&&next!=null){
              cur.next=next.next;
              next.next=cur;
              pre.next=next;
              pre=cur;
              cur=pre.next;
              next=cur==null?null:cur.next;
          }
                return dummyHead.next ;
        }
        //方法四
         public ListNode swapPairs(ListNode head) {
            if(head==null||head.next==null){
                 return head;
               }
               
            //将头结点的后继点设置为res
            ListNode res = head.next;
            //将res.next和res.next.next进行交换
            head.next = swapPairs(res.next);
            //原先的res与头结点相连接
            res.next = head;
            //返回对应的res
            return res;     
        }

[3a7163f8f24b01035ea7969c12640c4a.png]: https://img-blog.csdnimg.cn/img_convert/3a7163f8f24b01035ea7969c12640c4a.png
[aba60a5d09c616dd77a38e8115110003.png]: https://img-blog.csdnimg.cn/img_convert/aba60a5d09c616dd77a38e8115110003.png
[b5062f7f90e544db9377a4c7bf6e2a43.png]: https://img-blog.csdnimg.cn/b5062f7f90e544db9377a4c7bf6e2a43.png
[5f66a939ab68407a2d5988fb01ff98b7.gif]: https://img-blog.csdnimg.cn/img_convert/5f66a939ab68407a2d5988fb01ff98b7.gif
[8dc5f45b2b33c6054ce3e9e19544904e.gif]: https://img-blog.csdnimg.cn/img_convert/8dc5f45b2b33c6054ce3e9e19544904e.gif
[64f36f08498b59ce5f8080d7fb3e26ef.gif]: https://img-blog.csdnimg.cn/img_convert/64f36f08498b59ce5f8080d7fb3e26ef.gif
[ee948a770629324481d03910224129c2.gif]: https://img-blog.csdnimg.cn/img_convert/ee948a770629324481d03910224129c2.gif
[k]: https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/
[N]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
[Link 1]: https://leetcode.cn/problems/reverse-linked-list/
[Link 2]: https://leetcode.cn/problems/delete-node-in-a-linked-list/
[Link 3]: https://leetcode.cn/problems/swap-nodes-in-pairs/