首页 > 代码库 > Insert into a Cyclic Sorted List

Insert into a Cyclic Sorted List

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list. (increasing sorted)

 

We need to consider the following three cases:

1. pre->val <=x<=current->val:

insert between prev and current.

2. x is the maximum or minimum value in the list:

Insert before the head.

3. Traverses back to the starting point:

Insert before the starting point.

// aNode是引用,当aNode为空时,返回结点的指针void insert(Node*& aNode, int x){    if (!aNode)    {        aNode = new Node(x);        aNode->next = aNode;        return;    }    Node* p = aNode;    Node* prev = NULL;    do    {        prev = p;        p = p->next;        if (x <= p->data && x >= prev->data)            break;        if ((prev->data > p->data) && (x < p->data || x > pre->data))            break;    } while (p != aNode);    Node* newNode = new Node(x);    newNode->next = p;    prev->next = newNode;}

http://leetcode.com/2011/08/insert-into-a-cyclic-sorted-list.html

Insert into a Cyclic Sorted List