算法：链表（力扣+牛客经典题）

亦凉 2023-09-24 16:14 41阅读 0赞

## 链表 ##

## 力扣 ##

### 203. 移除链表元素 ###

![de6b645c70e74845a649df3c5379239b.png][]

#### 思路：使用while循环每找到指定的值，就把下一个节点指向下下个节点的位置 ####

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode removeElements(ListNode head, int val) {
        
            // 初始化链表 第一个值为0
            ListNode listNode = new ListNode(0,head);
            // 因为单链表是不可逆的，所以把listNode的 地址赋给 temp，就可以控制temp来操作链表，
            ListNode temp = listNode;
            // 循环找值，并去掉
            while (temp.next != null){
        
                if (temp.next.val == val){
        
                    // 如果temp.next有值，最不济temp.next.next为null，而把null重新赋给temp.next也不会报空节点异常
                    temp.next = temp.next.next;
                } else {
        
                    temp = temp.next;
                }
            }
            // 因为listNode的初始值为0，他的下一个才是原数组head（删掉了指定的值）
            return listNode.next;
        }
    }

### 206. 反转链表 ###

![在这里插入图片描述][52466ed6458e441ebac3120c32604993.png]

#### 思路：就是先设一个值为null，再用head开头的值指向这个null，再把head指向下一个，重复 ####

### 24. 两两交换链表中的节点 ###

![在这里插入图片描述][4d859382fd2b4be3a97c2ec7bddf7d4e.png]

#### 思路：每次找到要旋转的个数，并旋转，剩余的链表进入递归，并挨个拼接 ####

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            ListNode listNode = reverseKGroup(head, 2);
            return listNode;
        }
        public ListNode reverseKGroup (ListNode head, int k) {
        
            //找到每次翻转的尾部
            ListNode tail = head;
            //遍历k次到尾部
            for(int i = 0; i < k; i++){
        
                //如果不足k到了链表尾，直接返回，不翻转
                if(tail == null) {
        
                    return head;
                }
                tail = tail.next;
            }
            // 这里就是翻转链表的知识点
            //翻转时需要的前序和当前节点
            ListNode pre = null;
            ListNode cur = head;
            //在到达当前段尾节点前
            while(cur != tail){
        
                //翻转
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            //当前尾指向下一段要翻转的链表
            head.next = reverseKGroup(tail, k);
            return pre;
        }
    }

### 19. 删除链表的倒数第 N 个结点 ###

![在这里插入图片描述][f64a9792eb384d6386d7e7aaa68e214a.png]

#### 思路：使用双指针，先让前节点走N+1步，后节点不动，然后遍历前节点，直到前节点指向null的时候，后节点的节点指向倒数N个节点的前一个节点 ####

### 160.链表相交 ###

![在这里插入图片描述][8b30aabe7c0c45fabc9fbc57439722d5.png]

#### 思路：意思就是说两个链表后面节点可能相同，那么后面的长度也是一样的，就需要把前面长的链表给截成和短的链表一样长，然后进行比较，不一样就一起后移 ####

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            // 使用AL和BL记录两个链表的长度
            int AL = 0;
            int BL = 0;
            ListNode aL = headA;
            ListNode bL =headB;
            while (aL!=null){
        
                AL++;
                aL = aL.next;
            }
            while (bL!=null){
        
                BL++;
                bL = bL.next;
            }
            aL = headA;
            bL = headB;
            // 截取长的链表，使两个链表一样长
            if (AL > BL){
        
                for (int i = 0; i < AL - BL; i++) {
        
                    aL = aL.next;
                }
            }else {
        
                for (int i = 0; i < BL - AL; i++) {
        
                    bL = bL.next;
                }
            }
            // 循环比较是否相同，返回相同的部分
            while (aL!=null){
        
                if (aL == bL){
        
                    return aL;
                }
                aL = aL.next;
                bL = bL.next;
            }
            return null;
        }
    }

### 142.环形链表 II ###

![在这里插入图片描述][9e2171bfb0644db5911f963659e08f3a.png]

#### 思路：一、先要判断是否是循环链表；二、要找出循环入口节点 ####

#### 一判断是否循环 ####

##### 使用快慢指针，前指针每次走两个节点，后指针每次走一个节点，如果是循环链表的话，前一个指针会追上后一个指针的，可以做一下试验： #####

##### 如示例一：前走两步，后走一步 #####

##### 两个从三开始 #####

##### 第一次：前：2,0；后：2； #####

##### 第二次：前：-4,2；后：0； #####

##### 第三次：前：0,-4；后：-4； #####

##### 结束 #####

#### 二、要找出循环入口节点 ####

##### 先定位到判断循环链表的那个节点，如上诉的0这个节点，再从开头（3）走一个值，他们两个每次只走一步，如果他们相等的话，就是那个节点循环的头 #####

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode left = head;
            ListNode right = head;
            // 因为right要走两步，怕出现空指针异常（如果 right.next 为null的话，right.next.next就会空指针异常）
            while (right != null && right.next != null){
        
                // 判断是否循环
                left = left.next;
                right = right.next.next;
                if (left == right){
        
                    left = head;
                    // 找循环的头节点
                    while (left != right){
        
                        left = left.next;
                        right = right.next;
                    }
                    return left;
                }
            }
            return null;
        }
    }

## 牛客： ##

### **BM1** 反转链表（同力扣：206.循环链表，上面有讲） ###

### BM2 链表内指定区间反转 ###

![在这里插入图片描述][b2e70f6e9c2c414691f368b2c3d89358.png]

#### 思路：截取翻转，并连接 ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         *
         * @param head ListNode类
         * @param m int整型
         * @param n int整型
         * @return ListNode类
         */
        public ListNode reverseBetween (ListNode head, int m, int n) {
        
            //设置虚拟头节点
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
    
            ListNode pre = dummyNode;
            //1.走left-1步到left的前一个节点
            for(int i=0;i<m-1;i++){
        
                pre = pre.next;
            }
    
            //2.走roght-left+1步到right节点
            ListNode rigthNode = dummyNode;
            for(int i=0;i<n;i++){
        
                rigthNode = rigthNode.next;
            }
    
            //3.截取出一个子链表
            ListNode leftNode = pre.next;
            ListNode cur = rigthNode.next;
    
            //4.切断链接
            pre.next=null;
            rigthNode.next=null;
    
            //5.反转局部链表
            reverseLinkedList(leftNode);
    
            //6.接回原来的链表
            pre.next = rigthNode;
            leftNode.next = cur;
            return dummyNode.next;
        }
        //反转局部链表
        private void reverseLinkedList(ListNode head){
        
            ListNode pre = null;
            ListNode cur = head;
            while(cur!=null){
        
                //Cur_next 指向cur节点的下一个节点
                ListNode Cur_next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = Cur_next ;
            }
        }
    }

### BM3 链表中的节点每k个一组翻转（同力扣：24. 两两交换链表中的节点，上面有讲） ###

### BM4 合并两个排序的链表 ###

![在这里插入图片描述][d74e2e4282a14584973e44f87497c89e.png]

#### 思路：一直循环，比较两个链表当时的大小，小的那个加入新的链表，并指向后一个节点，大的链表不动，最后哪个链表还有剩的话，就自动加入后面就可以了 ####

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        
        public ListNode Merge(ListNode list1,ListNode list2) {
        
            ListNode listNode = new ListNode(-1);
            // 新的链表
            ListNode x = listNode;
            while (list1 != null&&list2!=null){
        
                // 判断哪个链表的节点大，把小的节点接入新的链表
                if (list1.val > list2.val){
        
                    x.next = list2;
                    x = x.next;
                    list2 = list2.next;
                }else {
        
                    x.next = list1;
                    x = x.next;
                    list1 = list1.next;
                }
            }
            //哪个链表还有剩，直接连在后面
            if(list1 != null)
                x.next = list1;
            else
                x.next = list2;
            return listNode.next;
        }
    }

### BM5 合并k个已排序的链表 ###

![在这里插入图片描述][a620022254224ce3aa3dfbb21688ac8c.png]

#### 思路：这里使用了PriorityQueue优先队列（最小堆），这个数据结构可以把最小值顶到堆的最前面，使用我只需要，把list里面的所有值放入最小堆里面，然后遍历最小堆，得到一个完整的新链表就可以了 ####

import java.util.*;
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
        
            // 优先队列（最小堆）
            Queue<Integer> queue = new PriorityQueue<>();
            // 加入最小堆里面
            lists.forEach(x->{
        
                while (x!=null){
        
                    queue.offer(x.val);
                    x = x.next;
                }
            });
            // 新建一个链表用来装遍历最小堆的最前面就可以了
            ListNode listNode = new ListNode(-1);
            ListNode x = listNode;
            while (!queue.isEmpty()){
        
                x.next = new ListNode(queue.poll());
                x = x.next;
            }
            return listNode.next;
        }
    }

### BM6 判断链表中是否有环（同力扣：142.环形链表 II的第一个观点寻找循环链表，上面有讲） ###

### BM7 链表中环的入口结点（同力扣：142.环形链表 II的第二个观点寻找循环链表入口节点，上面有讲） ###

### BM8 链表中倒数最后k个结点 ###

![在这里插入图片描述][2114d7a5b7b1478b9fc1de223e521b3e.png]

#### 思路：双指针，先让前节点走N+1步，后节点不动，然后遍历前节点，直到前节点指向null的时候，后节点的节点指向倒数N个节点的前一个节点 ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     *   public ListNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param pHead ListNode类 
         * @param k int整型 
         * @return ListNode类
         */
        public ListNode FindKthToTail (ListNode pHead, int k) {
        
            if (pHead==null){
        
                return pHead;
            }
            ListNode x = pHead;
            for (int i = 0; i < k; i++) {
        
                if (x == null){
        
                    return null;
                }
                x = x.next;
            }
            ListNode y = pHead;
            while (x != null){
        
                x = x.next;
                y = y.next;
            }
            return y;
        }
    }

### BM9 删除链表的倒数第n个节点（同力扣：19. 删除链表的倒数第 N 个结点，上面有讲） ###

### BM10 两个链表的第一个公共结点（同力扣：160.链表相交，上面有讲） ###

### BM11 链表相加(二) ###

![在这里插入图片描述][7d5f5539e5ee43a8996f75f5756785d8.png]

#### 思路：先翻转两个链表（因为加法都是从个位加着走，所以翻转一个从头一个加到尾，再翻转一下，就是我们需要的值），就是取到每个节点值相加，如果进位就往前加一个，如果到最后一个节点还需要进位，就再下一个节点输入一。 ####

import java.util.*;
    
    import java.math.BigInteger;
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        public ListNode addInList (ListNode head1, ListNode head2) {
        
            // 翻转
            ListNode a = reverse(head1);
            ListNode b = reverse(head2);
            // c是判断需要进位不，如果是0就是没进位，1就是需要进位的那个加上1
            int c = 0;
            // x是a链表节点的值
            int x = 0;
            // y是b链表节点的值
            int y = 0;
            // 通过d来记录listNode的地址，listNode变动的时候，d还是指向没变动的头结点
            ListNode listNode = new ListNode(-1);
            ListNode d = listNode;
            while (a!=null||b!=null){
        
                // 给x赋值
                if (a!=null){
        
                    x = a.val;
                    a = a.next;
                }else {
        
                    x = 0;
                }
                // 给y赋值
                if (b!=null){
        
                    y = b.val;
                    b = b.next;
                }else {
        
                    y = 0;
                }
                // 让listNode.next指向新建一个链表
                // (x+y+c)%10 可以得到个位的值，存入新的链表
                listNode.next = new ListNode((x+y+c)%10);
                listNode = listNode.next;
                // 判断是否进位 如果十位有值 c就位十位的值
                c = (x + y + c)/10;
            }
            // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
            if(c > 0){
        
                listNode.next = new ListNode(c);
            }
            // 再次翻转
            return reverse(d.next);
        }
    
        // 反转链表
        ListNode reverse(ListNode head){
        
            if(head == null) {
        
                return head;
            }
            ListNode cur = head;
            ListNode node = null;
            while(cur != null){
        
                ListNode tail = cur.next;
                cur.next = node;
                node = cur;
                cur = tail;
            }
            return node;
        }
    }

### BM12 单链表的排序 ###

![在这里插入图片描述][db54f566bc7b4f319c5c3dc212fa8a83.png]

#### 思路：一、变成数组然后排序重新写入链表；二、使用PriorityQueue优先队列（最小堆）排序取值就可以了 ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head ListNode类 the head node
         * @return ListNode类
         */
        public ListNode sortInList (ListNode head) {
        
            // 最小堆
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            // 存入最小堆
            while (head!=null){
        
                queue.add(head.val);
                head = head.next;
            }
            ListNode listNode = new ListNode(-1);
            ListNode x = listNode;
            // 从最小堆取值，然后组成新的数组
            while (!queue.isEmpty()){
        
                listNode.next = new ListNode(queue.poll());
                listNode = listNode.next;
            }
            return x.next;
        }
    }

### BM13 判断一个链表是否为回文结构 ###

![在这里插入图片描述][2b71a9315c6540cd9132f72ba23b48ac.png]

#### 思路：把链表的值写入一个数组里面，然后利用双指针判断是否是回文就可以了（就是第一个指针指向头，后一个指针指向尾，判断是否相等，相等就向前比较就可以了） ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head ListNode类 the head
         * @return bool布尔型
         */
        public boolean isPail (ListNode head) {
        
            ArrayList<Integer> list = new ArrayList<>();
            // 变成一个list集合
            while (head!=null){
        
                list.add(head.val);
                head = head.next;
            }
            int x = 0;
            int y = list.size() - 1;
            // 双指针判断是否为回文
            while (x<y){
        
                if (!list.get(x++).equals(list.get(y--))){
        
                    return false;
                }
            }
            return true;
        }
    }

### BM14 链表的奇偶重排 ###

![在这里插入图片描述][38636904db804baca5207e3aa3a041f5.png]

#### 思路：看代码 ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     *   public ListNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    public class Solution {
        
        public ListNode oddEvenList (ListNode head) {
        
            //如果链表为空，不用重排
            if(head == null) 
                return head;
            //even开头指向第二个节点，可能为空
            ListNode even = head.next; 
            //odd开头指向第一个节点
            ListNode odd = head; 
            //指向even开头
            ListNode evenhead = even; 
            while(even != null && even.next != null){
        
                //odd连接even的后一个，即奇数位
                odd.next = even.next; 
                //odd进入后一个奇数位
                odd = odd.next; 
                //even连接后一个奇数的后一位，即偶数位
                even.next = odd.next; 
                //even进入后一个偶数位
                even = even.next; 
            } 
            //even整体接在odd后面
            odd.next = evenhead; 
            return head;
        }
    }

### BM15 删除有序链表中重复的元素-I ###

![在这里插入图片描述][a3c51d92a10045a18361ced04aff5b96.png]

#### 思路：因为是有序的，所以只要后一个节点的值与自己节点一样，把后一个节点指向下下个节点就可以了 ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head ListNode类 
         * @return ListNode类
         */
        public ListNode deleteDuplicates (ListNode head) {
        
            // write code here
            ListNode a = head;
            while (head!=null && head.next!=null){
        
                // 如果后一个节点和自己节点值相等的话，就删除掉，并不需要移动自己的指针
                if (head.val == head.next.val){
        
                    head.next = head.next.next;
                    continue;
                }
                head = head.next;
            }
            return a;
        }
    }

### BM16 删除有序链表中重复的元素-II ###

![在这里插入图片描述][81cd3580235b4b35b390360608a9e952.png]

#### 思路：添加一个表头，然后看下一个节点与下下个节点是否相同，如果相同，再循环看看后面的节点的值是否一样，相同就全部跳过 ####

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head ListNode类 
         * @return ListNode类
         */
        public ListNode deleteDuplicates (ListNode head) {
        
            //空链表
            if(head == null)
                return null;
            ListNode res = new ListNode(0);
            //在链表前加一个表头
            res.next = head;
            ListNode cur = res;
            while(cur.next != null && cur.next.next != null){
        
                //遇到相邻两个节点值相同
                if(cur.next.val == cur.next.next.val){
        
                    int temp = cur.next.val;
                    //将所有相同的都跳过
                    while (cur.next != null && cur.next.val == temp)
                        cur.next = cur.next.next;
                }
                else
                    cur = cur.next;
            }
            //返回时去掉表头
            return res.next;
        }
    }

[de6b645c70e74845a649df3c5379239b.png]: https://img-blog.csdnimg.cn/de6b645c70e74845a649df3c5379239b.png
[52466ed6458e441ebac3120c32604993.png]: https://img-blog.csdnimg.cn/52466ed6458e441ebac3120c32604993.png
[4d859382fd2b4be3a97c2ec7bddf7d4e.png]: https://img-blog.csdnimg.cn/4d859382fd2b4be3a97c2ec7bddf7d4e.png
[f64a9792eb384d6386d7e7aaa68e214a.png]: https://img-blog.csdnimg.cn/f64a9792eb384d6386d7e7aaa68e214a.png
[8b30aabe7c0c45fabc9fbc57439722d5.png]: https://img-blog.csdnimg.cn/8b30aabe7c0c45fabc9fbc57439722d5.png
[9e2171bfb0644db5911f963659e08f3a.png]: https://img-blog.csdnimg.cn/9e2171bfb0644db5911f963659e08f3a.png
[b2e70f6e9c2c414691f368b2c3d89358.png]: https://img-blog.csdnimg.cn/b2e70f6e9c2c414691f368b2c3d89358.png
[d74e2e4282a14584973e44f87497c89e.png]: https://img-blog.csdnimg.cn/d74e2e4282a14584973e44f87497c89e.png
[a620022254224ce3aa3dfbb21688ac8c.png]: https://img-blog.csdnimg.cn/a620022254224ce3aa3dfbb21688ac8c.png
[2114d7a5b7b1478b9fc1de223e521b3e.png]: https://img-blog.csdnimg.cn/2114d7a5b7b1478b9fc1de223e521b3e.png
[7d5f5539e5ee43a8996f75f5756785d8.png]: https://img-blog.csdnimg.cn/7d5f5539e5ee43a8996f75f5756785d8.png
[db54f566bc7b4f319c5c3dc212fa8a83.png]: https://img-blog.csdnimg.cn/db54f566bc7b4f319c5c3dc212fa8a83.png
[2b71a9315c6540cd9132f72ba23b48ac.png]: https://img-blog.csdnimg.cn/2b71a9315c6540cd9132f72ba23b48ac.png
[38636904db804baca5207e3aa3a041f5.png]: https://img-blog.csdnimg.cn/38636904db804baca5207e3aa3a041f5.png
[a3c51d92a10045a18361ced04aff5b96.png]: https://img-blog.csdnimg.cn/a3c51d92a10045a18361ced04aff5b96.png
[81cd3580235b4b35b390360608a9e952.png]: https://img-blog.csdnimg.cn/81cd3580235b4b35b390360608a9e952.png