Java&C++题解与拓展——leetcode剑指OfferII 029.排序的循环链表【么的新知识】

• 题目要求
• 思路：模拟
• • Java
  • C++
• 总结

• 在有序的链表中找到合适的插入位置然后插入即可；
• 先构造一个指向自己的插入值节点 i n s e r t N o d e insertNode insertNode；
• 当链表为空时返回自己；
• 当链表中只有一个节点直接插入；
• 遍历所有节点，找一个合适的位置，也就是当前节点 c u r cur cur的值小于 i n s e r t V a l insertVal insertVal，但是下一节点值大于 i n s e r t V a l insertVal insertVal；
  • 注意在循环链表最大值和最小值的交界处的特殊判断，大于最大值或小于最小值就在这个交界插入。

class Solution {
    public Node insert(Node head, int insertVal) {
        Node insertNode = new Node(insertVal);
        insertNode.next = insertNode;
        if (head == null)
            return insertNode;
        if (head.next == head) {
            head.next = insertNode;
            insertNode.next = head;
            return head;
        }
        Node cur = head;
        while (cur.next != head) {
            if (insertVal >= cur.val && insertVal <= cur.next.val)
                break;
            if (cur.val > cur.next.val) {
                if (insertVal > cur.val || insertVal < cur.next.val)
                    break;
            }
            cur = cur.next;
        }
        insertNode.next = cur.next;
        cur.next = insertNode;        
        return head;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node *insertNode = new Node(insertVal);
        insertNode->next = insertNode;
        if (head == nullptr)
            return insertNode;
        if (head->next == head) {
            head->next = insertNode;
            insertNode->next = head;
            return head;
        }
        Node *cur = head;
        while (cur->next != head) {
            if (insertVal >= cur->val && insertVal <= cur->next->val)
                break;
            if (cur->val > cur->next->val) {
                if (insertVal > cur->val || insertVal < cur->next->val)
                    break;
            }
            cur = cur->next;
        }
        insertNode->next = cur->next;
        cur->next = insertNode;        
        return head;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

快乐的链表模拟题，有一次感觉不至于中等……

【今天么的rust可写，赶紧去肝论文了。】