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

链接 ：牛客面试必刷TOP101

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

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

题目要求

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

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

题目分析（栈）

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)

题目要求

题目分析

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

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

上代码（穿针引线）

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)

题目要求

题目分析

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

上代码

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)

题目要求

题目分析

（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)

题目要求

题目分析

（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

然后开始合并，这就和上一题一样了

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