【刷题笔记】之牛客面试必刷TOP101（1）

Bertha 。 2023-09-28 18:39 32阅读 0赞

**目录**

1. 反转链表（双链表头插法 / 栈）

2.链表内指定区间反转

3. 链表中的节点每k个一组翻转

4. 合并两个排序的链表

5. 合并k个已排序的链表

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

> **链接 ：[牛客面试必刷TOP101][TOP101]**

## 1. 反转链表（双链表头插法 / 栈） ##

题目链接 [反转链表\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

题目要求

![b9800f682d9e42189b10da892fb54ba7.png][]

题目分析（新建链表头插法）

![37feb23f8eff4f938948b029a2b638af.png][]

public class Solution {
        public ListNode ReverseList(ListNode head) {
            ListNode newHead = null;
            while(head != null) {
                ListNode tmp = head.next;
                //使用头插法
                head.next = newHead;
                newHead = head;
                head = tmp;
            }
            return newHead;
        }
    }

题目分析（栈）

![d32ffa25298745c99cdf7aafc77d46d9.png][]

import java.util.Stack;
    
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            Stack<ListNode> stack = new Stack<>();
            //入栈
            while(head != null) {
                stack.push(head);
                head = head.next;
            }
            if(stack.isEmpty()) {
                return null;
            }
            //出栈
            ListNode node = stack.pop();
            ListNode newHead = node;
            while(!stack.isEmpty()) {
                ListNode tmpNode = stack.pop();
                //建链表
                node.next = tmpNode;
                node = node.next;
            }
            //走到这里栈空 新链表建成
            node.next = null;
            return newHead;
        }
    }

## 2.链表内指定区间反转 ##

题目链接 [链表内指定区间反转\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 1]

题目要求

![42e93091497c4fafa2c8334e431641e8.png][]

题目分析

![3a03a32aff2a4f2a9e4972839566f6a1.png][]

**上代码（保存结点位置，切断链表，反转链表，再连接）**

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //1.建立虚拟头结点
        ListNode temp = new ListNode(-1);
        temp.next = head;
        
        //2.记录n的前一个节点
        ListNode pro = temp;
        for(int i = 0; i < m-1; i++) {
            pro = pro.next;
        }
        
        //3.找到n位置下的结点
        ListNode nNode = pro;
        for(int i = 0; i < n-m+1; i++) {
            nNode = nNode.next;
        }
        
        //4.记录m位置下的结点，和n后下一个结点的位置
        ListNode mNode = pro.next;
        ListNode cur = nNode.next;
        
        //5.断开m到n之间的连接
        pro.next = null;
        nNode.next = null;
        
        //6.反转m到n之间的链表
        reverseList(mNode);
        
        //7.连接反转后的子链表
        pro.next = nNode;
        mNode.next = cur;
        return temp.next;
        }
        
        //反转链表
        public ListNode reverseList(ListNode head){
            //取一个新的头结点
            ListNode newHead = null;
            while(head != null) {
            ListNode cur = head.next;
                //头插法
                head.next = newHead;
                newHead = head;
                head = cur;
            }
            return newHead;
        }
    }

**上代码（穿针引线）**

![cc9ddbede78e43728324355e8e97289f.png][]

import java.util.*;
    
    public class Solution {
        //3.穿针引线
        public ListNode reverseBetween (ListNode head, int m, int n) {
            //1.设置虚拟头结点
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            
            //2.记录m前的一个节点
            ListNode pro = dummyNode;
            for(int i = 0; i < m-1; i++) {
                pro = pro.next;
            }
            
            //3.记录待反转的第一个结点和这个节点的下一个节点的位置
            ListNode cur = pro.next;
    
            //4.开始穿针引线
            for(int i = 0; i < n-m; i++) {
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = pro.next;
                pro.next = next;
            }
            return dummyNode.next;
        }
    }

## 3. 链表中的节点每k个一组翻转 ##

题目链接 [链表中的节点每k个一组翻转\_牛客题霸\_牛客网 (nowcoder.com)][k_ _nowcoder.com]

题目要求

![80b33804555842888995f3537d870ceb.png][]

**题目分析**

**(1)直接暴力解法，根据K给链表分组，然后子链表反转，再重新连接子链表**

![3b8c01d8dde9497aa3f2543bc722dfb5.png][]

上代码

public class Solution {
        /**
         * 
         * @param head ListNode类 
         * @param k int整型 
         * @return ListNode类
         */
        public ListNode reverseKGroup (ListNode head, int k) {
            //创建虚拟结点
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            
            //创建两个节点，分别表示每个分组的前一个和后一个节点
            ListNode pre = dummy;
            ListNode end = dummy;
            
            while(end.next != null) {
                //每k个一组反转，【pre，end】
                for(int i = 0; i < k & end != null; i++) {
                    end = end.next;
                }
                //如果end为空，说明不满一组
                if(end == null) {
                    break;
                }
                //记录每组的头结点，和下一组的头结点
                ListNode start = pre.next;
                ListNode next = end.next;
                
                //断开连接，进行分组反转
                end.next = null;
                pre.next = reverseList(start);
                
                //反转之后重新连接
                start.next = next;
                
                //重新给pre和end赋值
                pre = start;
                end = start;
            }
            return dummy.next;
        }
        
        //反转链表
        private ListNode reverseList(ListNode head){
            ListNode newHead = null;
            while(head != null) {
                ListNode temp = head.next;
                head.next = newHead;
                newHead = head;
                head = temp;
            }
            return newHead;
        }
    }

**（2）也可以使用栈来做**

**创建栈 先入栈，每次判断是否够k个节点，如果够，就出栈到新的链表中。如果不够就返回**

**每次要把第k+1个结点记住，因为后面要把每次出完栈的子链表连接在一起**

public ListNode reverseKGroup (ListNode head, int k) {
            if(head == null) {
                return head;
            }
            //1.创建栈，创建虚拟头结点
            Stack<ListNode> stack = new Stack<>();
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode pre = dummy;
            int n = k;
            
            while(pre != null && pre.next != null) {
                ListNode temp = pre.next;
                //2.入栈
                while(temp != null && n > 0) {
                    stack.add(temp);
                    temp = temp.next;
                    n--;
                }
                
                //3.记录第k+1个结点，用作连接
                ListNode nextNode = stack.peek().next;
                
                //4.n=0,说明栈中刚好k个结点，出栈连接
                if(n == 0) {
                    while(!stack.empty()) {
                        pre.next = stack.pop();
                        pre = pre.next;
                    }
                }else {
                    break;
                }
                //5.连接
                pre.next = nextNode;
                n = k;
            }
            return dummy.next;
        }

## **4. 合并两个排序的链表** ##

题目链接 [合并两个排序的链表\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 2]

题目要求

![69099c0931ab462892673454eab5b04c.png][]

题目分析

> **（1）直接迭代**
> 
> **1.创建一个虚拟头结点，然后再来一个节点prev指向虚拟头结点**
> 
> **2.两个链表头结点先比较，小的结点，放在prev后面，然后这条链表节点向后走一位**
> 
> **3.继续重复比较，每放一个节点prev向后走一位**
> 
> **4.直到某一条链表为null，剩下的这个链表直接连在prev后面**

上代码

public ListNode Merge(ListNode list1,ListNode list2) {
            ListNode newHead = new ListNode(-1);
            ListNode prev = newHead;
            
            while(list1 != null && list2 != null) {
                if(list1.val <= list2.val) {
                    prev.next = list1;
                    list1 = list1.next;
                } else {
                    prev.next = list2;
                    list2 = list2.next;
                }
                prev = prev.next;
            }
            //合并之后，谁还有剩余的就连在prev的后面
            prev.next = list1 == null ? list2:list1;
            return newHead.next;
        }

> **方法二：递归** **先分一下**
> 
> **情况1.两条链表一条为空，另一条不为空，直接返回不为null的链表**
> 
> **情况2.刚开始两条链表头结点比较，小的结点1的那条链表，就可以想象成确定了的（也可以想象成这个节点就是结果中的结点），然后继续往下递归比较，直到出现情况1的条件**

public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1 == null) {
                return list2;
            }else if(list2 == null) {
                return list1;
            }else if(list1.val < list2.val) {
                list1.next = Merge(list1.next,list2);
                 return list1;
            }else {
               list2.next = Merge(list1,list2.next);
               return list2;
            }
        }

## **5. 合并k个已排序的链表**  ##

**题目链接** [合并k个已排序的链表\_牛客题霸\_牛客网 (nowcoder.com)][k_ _nowcoder.com 1]

**题目要求**

![e0aee4f1d4024e00ab37c74f3c6195ed.png][]

**题目分析**

> **（1）最暴力直接的解法就是，两个两个合并**
> 
> **既然已经给了K个已经排好序的链表，那么for循环，让每两个链表合并之后，就和下一个合并**
> 
> **两个链表合并，上一个题已经写过了，可以迭代也可以递归**
> 
> **但是这样两个合并的方法，可能会超时（如果链表特别多的情况下），不建议使用**

**上代码**

public ListNode mergeKLists(ArrayList<ListNode> lists) {
            ListNode ans = null;
            for(int i = 0; i < lists.size(); i++) {
                ans = mergeTwoList(ans,lists.get(i));
            }
            return ans;
        }
        
        private ListNode mergeTwoList(ListNode l1,ListNode l2){
            if(l1 == null || l2 == null) {
                return l1 == null ? l2:l1;
            }
            ListNode newHead = new ListNode(0);
            ListNode tmp = newHead;
            while(l1 != null && l2 != null) {
                if(l1.val <= l2.val) {
                    tmp.next = l1;
                    l1 = l1.next;
                }else {
                    tmp.next = l2;
                    l2 = l2.next;
                }
                tmp = tmp.next;
            }
            tmp.next = (l1 == null) ? l2:l1;
            return newHead.next;
        }

> **（2）分治（归并排序）**
> 
> **题中给的是ArrayList类型的链表数组**
> 
> **定义left和right分别指向这个链表数组的左右两边进行分组，往下递归直到left==right**
> 
> **然后开始合并，这就和上一题一样了**

![d96a08bfbc7a404ebc4bee9e13efcd25.png][]

public class Solution {
        //合并
        private ListNode Merge (ListNode list1,ListNode list2) {
            if(list1 == null) {
                return list2;
            }
            if(list2 == null) {
                return list1;
            }
            ListNode newHead = new ListNode(0);
            ListNode cur = newHead;
            //两个链表都不为null
            while(list1 != null && list2 != null) {
                //取出较小值的结点
                if(list1.val <= list2.val) {
                    cur.next = list1;
                    list1 = list1.next;
                }else {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = (list1 == null) ? list2 : list1;
            return newHead.next;
        }
        //划分区间
        private ListNode divideMerge(ArrayList<ListNode> lists,int left, int right) {
            if(left > right){
                return null;
            }else if(left == right) {
                return lists.get(left);
            }
            int mid = left + (right-1)/2;
            return Merge(divideMerge(lists,left,mid),divideMerge(lists,mid+1,right));
        }
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
           //k个链表归并排序
            return divideMerge(lists,0,lists.size()-1);
        }
    }

> **（3）使用优先级队列，本质上就是堆，内置的是小根堆**
> 
> **1.创建一个优先级队列，并且还要重载比较方法，构造一个比较链表结点值的小根堆**
> 
> **2.然后遍历每个链表的头，将不为null的结点加入的优先级队列中**
> 
> **3.加一个虚拟头结点，将每次从堆顶取出来的元素，加入到虚拟头结点的后面**
> 
> **4.每次从堆顶取出一个元素后，就要给堆中重新放入刚刚取出来的结点的下一个结点。并且还要判空**

//使用优先级队列
         public ListNode mergeKLists(ArrayList<ListNode> lists) {
             Queue<ListNode> pq = new PriorityQueue<>(
             (v1,v2) -> v1.val - v2.val);
             for(int i = 0; i < lists.size(); i++) {
                 //不为null,就加入小根堆
                 if(lists.get(i) != null) {
                     pq.add(lists.get(i));
                 }
             }
             //加一个虚拟头结点
             ListNode newHead = new ListNode(-1);
             ListNode cur = newHead;
             while(!pq.isEmpty()){
                 //小根堆，取出就是最小的元素
                 ListNode temp = pq.poll();
                 //连接
                 cur.next = temp;
                 cur = cur.next;
                 //每次取出堆顶元素后，再放入链表的下一个元素进入小根堆
                 if(temp.next != null) {
                     pq.add(temp.next);
                 }
             }
             return newHead.next;
         }

[TOP101]: https://www.nowcoder.com/exam/oj
[_nowcoder.com]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
[b9800f682d9e42189b10da892fb54ba7.png]: https://img-blog.csdnimg.cn/b9800f682d9e42189b10da892fb54ba7.png
[37feb23f8eff4f938948b029a2b638af.png]: https://img-blog.csdnimg.cn/37feb23f8eff4f938948b029a2b638af.png
[d32ffa25298745c99cdf7aafc77d46d9.png]: https://img-blog.csdnimg.cn/d32ffa25298745c99cdf7aafc77d46d9.png
[_nowcoder.com 1]: https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
[42e93091497c4fafa2c8334e431641e8.png]: https://img-blog.csdnimg.cn/42e93091497c4fafa2c8334e431641e8.png
[3a03a32aff2a4f2a9e4972839566f6a1.png]: https://img-blog.csdnimg.cn/3a03a32aff2a4f2a9e4972839566f6a1.png
[cc9ddbede78e43728324355e8e97289f.png]: https://img-blog.csdnimg.cn/cc9ddbede78e43728324355e8e97289f.png
[k_ _nowcoder.com]: https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tqId=722&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
[80b33804555842888995f3537d870ceb.png]: https://img-blog.csdnimg.cn/80b33804555842888995f3537d870ceb.png
[3b8c01d8dde9497aa3f2543bc722dfb5.png]: https://img-blog.csdnimg.cn/3b8c01d8dde9497aa3f2543bc722dfb5.png
[_nowcoder.com 2]: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[69099c0931ab462892673454eab5b04c.png]: https://img-blog.csdnimg.cn/69099c0931ab462892673454eab5b04c.png
[k_ _nowcoder.com 1]: https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[e0aee4f1d4024e00ab37c74f3c6195ed.png]: https://img-blog.csdnimg.cn/e0aee4f1d4024e00ab37c74f3c6195ed.png
[d96a08bfbc7a404ebc4bee9e13efcd25.png]: https://img-blog.csdnimg.cn/d96a08bfbc7a404ebc4bee9e13efcd25.png