Search My Blog

Saturday, June 9, 2012

Insert into a Cyclic Sorted List

Problem : insert a given value into a sorted circular linked list, given a node in the list
(http://www.leetcode.com/2011/08/insert-into-a-cyclic-sorted-list.html)

Solution:

void insert(Node start, int val)
{
Node tmp = new Node(val);

//if list is empty
if(start == null) { tmp.next = tmp; return; }

//initialize current and greatest pointers
Node current = start;
Node greatest = start;

while(current.next != start)
{
//case 1: node lies between 2 values already present in the list
if(val > current.data && val greatest.data) greatest = current;
}

//now, value is either greater than all values in the list, or smaller than all values. //in any case, value should be inserted after the greatest node
tmp.next = greatest.next;
greatest.next = tmp;

}

No comments:

Post a Comment