Write an algorithm to insert a new value into a circular sorted linked list.

Question

Programming INterview · Accepted Answer

public void InsertCircular(List head, int value) {
	List current = head;
	if (value > head.value) {
		current = head;
		while(current.value < value && current.value < current.next.value) {
			current = current.next;
		}
		
	} else {
		while(current.value < current.next.value) {
			current = current.next;
		}
		//go to largest value
		while(current.next.value < value) {
			current = current.next;
		}
	}
	ListNode addedNode = new ListNode(value);
	addedNode.next = current.next;
	current.next = addedNode;
}
See more videos at youtube.com/user/programminginterivew

Hodge · Answer

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
struct Node 
{
	int val;
	Node * next;
};
void List::insert(Node * n)
{
	if(head == NULL)
	{
		head = n;
		n -> next = NULL
		return;
	}
	if(head -> val  val)
	{
		n -> next = head;
		head = n;
		return;
	}
	while(tmp -> next != NULL && tmp -> next -> val  val)
	{
		tmp = tmp -> next;
	}
	if(tmp - > next == NULL)
	{
		tmp -> next = n;
		n -> next = NULL;
	}
	else
	{
		n -> next = tmp -> next;
		tmp -> next = n;
	}
	return;
}

Zshen · Answer

class Node
{
   public:
   Node* next;
   int value;
   Node(int v)
   {
        value=v;
        next=NULL;
   }
};
void InsertNode(Node* head, int value)
{
    if(!head)
   {
        head=new Node(value);
        head=head->next;
        return;    
   }
   Node* node=head;
   if(node->value>value)// Update head pointer
   {
         //trick is firstly insert after the head, then swap it 
         Node*tmpNode= node->next;
         node->next= new Node(value);
         node->next->next=tmpNode;

         int tmp=node->next->value;
         node->next->value=node->value;
         node->value=tmp;

         return;
   }
   while(node->next!=head)
   {
         if(node->next->value>value)
         {
               Node*tmpNode=node->next;
               node->next=new Node(value);
               node->next->next=tmpNode;
               return;
         }
		 node=node->next;
   }
   Node*tmpNode=node->next;
   node->next=new Node(value);
   node->next->next=tmpNode;
   return;
}

Anonimo · Answer

http://www.youtube.com/user/programminginterview

Google

Domanda di colloquio di Google

Risposte di colloquio

Aziende seguite

Ricerche di lavoro