[数据结构与算法]剑指 Offer II 029. 排序的循环链表

力扣打卡：剑指 Offer II 029. 排序的循环链表

解题思路

目前为止，做过的最恶心的题目，明明逻辑就是很简单，但细节一直扣扣扣

• 如果 head==null 那么构造节点返回
• 找出最小值，并且是从 head 开始多个相等的最小值的最后一个
• 找到最小值，并且是从 head 开始多个相等的最小值的第一个，同时记录第一个最小值的前一个节点 prev
• 如果 insertVal <= min.val ，那么直接在第一个节点的前一个节点prev后插入即可
• 如果 insertVal > min.val，那么遍历一边环串，条件是从最后一个最小值开始，不经过第一个最小值，找出位置进行插入
• 返回即可

代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
    public Node insert(Node head, int insertVal) {
        if(head==null){
            head = new Node(insertVal);
            head.next = head;
            return head;
        }
        // 先找出最小值，再进行判断即可
        Node node = head.next;
        Node min = head;
        while(node!=head){
            min = min.val < node.val ? min : node; // 从head开始找到最小值，并且是找到最小值的最后一个
            node = node.next;
        }
        Node prev = min; // 最后一个最小值设置为prev
        node = min.next; // 从最后一个最小值开始找到第一个最小值
        while(node.val!=min.val) {prev=prev.next; node=node.next;} // 条件结束时node为第一个最小值，prev为第一个最小值的前一个节点
        
        if(insertVal<=min.val){ // 如果小于等于最小值的数，那么直接添加
            prev.next = new Node(insertVal);
            prev = prev.next;
            prev.next = node;
            return head;
        }
        Node p = min;
        node = min.next;
        while(node.val!=min.val){ // 想象成一个环，从最小值开始找，找出 insertVal>=node.val的最大位置
        	if(insertVal>=node.val) p = node;
            node = node.next;
        }
        node = p.next;
        p.next = new Node(insertVal);
        p = p.next;
        p.next = node;
        return head;
    }
}