malcolm.carvalho
BAN USERstruct Node {
int data; //digit
struct Node* next;
}
class LinkedList {
private:
Node* head;
public:
void AddOne();
}
void LinkedList::AddOne(){
if (head == null)
throw InvalidOperationException;
Node* cur = head;
Node* prev = null;
while (cur && cur->data == 9) {
cur->data = 0;
prev = cur;
cur = cur->next;
}
if (cur)
cur->data += 1;
else
prev->next = new Node(1, null);
}
// assuming LinkedList has a head Node member
void LinkedList::rotate(int k) {
Node* cur = head; Node* prev = null;
for (int i = 1; i < k && cur->next; ++i) {
prev = cur;
cur = cur->next;
}
if (prev && i == k) {
prev->next = 0;
Node* oldHead = head;
head = cur;
while (cur->next)
cur = cur->next;
cur-next = oldHead;
}
}
void insertValue(Node* head, Node* newNode)
{
int val = newNode->data;
if (head->next != head)
// list has more than one node
{
while (true)
{
if ( (head->data <= val && head->next->data >= val)
|| (head->data <= val && head->data >= head->next->data) )// check for the node whose next is head again
break;
else
{
head = head->next;
}
}
}
newNode->next = head->next;
head->next = newNode;
}
The basic code is to check whether the inserted node value lies between the current node and the next node. If so, insert the node and set the next pointers accordingly.
Two special cases need to be handled:
1. The list has a single node. In this case, we just set the next of the single node an the new node to each other.
2. The node to be inserted has a value between the head and the node preceding it. For this, I have the following check:
head->data <= val && head->data >= head->next->data;
- malcolm.carvalho September 10, 2017