Insert value into a circle linked list

April 21, 2016

Work on an algorithm called "Insert value into a circle linked list"


http://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/

another problem:

Insert into a cyclic sorted list:

http://articles.leetcode.com/insert-into-a-cyclic-sorted-list/

Question and Answer:
1. Three cases:

1. prev→val ≤ x ≤ current→val:

Insert between prev and current.

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

   Insert before the head. (ie, the head has the smallest value and its prev→val > head→val.

3. Traverses back to the starting point:

   Insert before the starting point.

2. Let us walk through the code, and put some comment:

void insert(Node *& aNode, int x) {

  if (!aNode) { // Julia: if the node is empty, then, create one, link to itself to form a loop

    aNode = new Node(x);

    aNode->next = aNode;

    return;

  }

  Node *p = aNode; // Julia: two pointers, one is current, one is previous, get into a loop

  Node *prev = NULL;

  do {

    prev = p;

    p = p->next;

int[] arr = new int[2]{prev->data, p->data}; // Julia: add some explanation variable

    if (x >= arr[0] && x <= arr[1] ) break;   // For case 1)

    if ((arr[0] > arr[1]) && (x > arr[0] || x < arr[1] )) break; // For case 2)

  } while (p != aNode);   // when back to starting point, then stop. For case 3)

  Node *newNode = new Node(x);

  newNode->next = p;

  prev->next = newNode;

}