Insert Num in Circle List

发表于 | 分类于

Insert Num To Circle List（向环链表中插入节点）

题目描述：

给定一个链表的头节点，和一个目标值。已知该链表从头部开始不降序，且最后一个节点指向了头节点；要求将该值插入链表后并保持链表仍旧有序。

例子：

1->3->4->1将节点5插入链表后得到1->3->4->5->1。

解题思路：

首先判断链表头节点是否为空，如果是空的情况，我们就将插入节点自己形成环链表返回即可。不为空的情况下，我们将pre指向head，将cur指向head->next。然后判断插入值和pre以及cur节点之间的关系。如果在二者之间我们就将数据插入即可；如果不是则继续向下遍历；当遍历一圈之后，如果都没找到合适的节点插入，说明这个插入值不是比所有的节点小，就是比所有的节点大。插入到头节点的上一个节点即可。注意这两种情况虽然进行操作一样，但是返回的头结点不一样。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class insertNum1{
public:
    ListNode* insertNum(ListNode* head, int num){
        ListNode* node = new ListNode(num);
        if (head == NULL){
            node->next = node;
            return node;
        }  // 头节点为空情况
        ListNode* pre = head;
        ListNode* cur = head->next;//记录前后两个节点用于遍历链表
        while(cur != head){
            if (pre->val <= num && cur->val >= num){
                break;  //该情况跳出循环然后插入节点
            }else{
                cur = cur->next;
                pre = cur; //不然继续遍历即可
            }
        }
        pre->next = node;
        node->next = cur;
        return head->val < num ? head : node;//不同情况返回不同头结点
    }
};