Cisco Systems Interview Question
Software Engineer / DevelopersCountry: United States
this is simple algo ,traverse the list ,delete the node whenever value matches.
start node is special case which is handled saperatly .
void delete(int x,node *start)
{
node *current=start;
while(current)
{
if(current->value==x) //if we have to delete start node
{
if(current==start)
{
node *temp=start;
current=current->next;
start=current;
delete(node);
}
else
{
node *temp=current->next;
current->value=current->next->value;
current->next=current->next->next;
current=current->next;
delete(temp);
}
}
}
The code above has a bug for deleting the last element. Also, it's a dead-loop because there's no current=current.next statement at the end of the while loop.
hey thanx for pointing out about bug to delete last element, but its not dead loop as in both if and else current=current is there, have a look again
What if the first if condition is not satisfied i.e. current->value and x do not equal?Won't we require a current=current->next in the else part of 1st if?
Recursion wud be the best to solve this with the least lines of code.
// Main Call
public void deleteMatching(int value){
if(head == null)
return;
else{
Node newNode = head.nextNode;
deleteMatching(newNode,value);
}
}
//Recurse Call
public void deleteMatching(Node toDelete,int value){
if(toDelete.nextNode.value == value){
Node newNext = toDelete.nextNode.nextNode;
toDelete.nextNode = newNext;
}
else{
toDelete = toDelete.nextNode;
deleteMatching(toDelete,value);
}
}
there is another big bug for this code, start=current will not change pointer after the function is over, we should use a 'return to the first node', or use reference of the pointer.
public static LinkedListNode delete_given_number(LinkedListNode head,int givenNumber){
if(head==null){
return null;
}
while(head.data==givenNumber){
head=head.next;
if(head==null){
return null;
}
}
LinkedListNode pervious=head;
LinkedListNode current=head;
while(current!=null){
if(current.data==givenNumber){
pervious.next=current.next;
}
else{
pervious=current;
}
current=current.next;
}
return head;
}
Full working code : awesomecoder.blogspot.com/2012/08/delete-all-matching-elements-in-linked.html
Node* deleteNode(Node* head,int data){
Node* temp;
Node* n;
temp = head;
while(temp != NULL){
if(temp->data == data){
head = temp->next;
temp->next = NULL;
free(temp);
temp = head;
continue;
}
n = temp->next;
if(n != NULL && n->data == data){
temp->next = n->next;
n->next = NULL;
free(n);
continue;
}
if(n == NULL){
break;
} else {
temp = temp->next;
}
}
return head;
}
Here's a solution which works for Nodes<ValueType>
static <ValueType> Node<?> remove(Node<?> head, final ValueType targetValue) {
Node<?> start = head;
//System.out.println("Target value: " + targetValue);
// handle base cases
if (head == null) {
return null;
} else if ((head != null) && (head.next == null) &&
targetValue.equals(head.value)) {
return null;
} else if ((head != null) && (head.next != null) &&
(head.next.next == null) && targetValue.equals(head.value)) {
return start = head.next;
}
//System.out.println("Start b4 loop: " + start);
//System.out.println("Head b4 loop: " + head);
while (head != null) {
//printList(start);
if (targetValue.equals(head.value)) {
head = head.next;
start = head;
} else if (head.next!=null && targetValue.equals(head.next.value)) {
head.next = head.next.next;
} else {
head = head.next;
}
//System.out.println("Start post loop: " + start);
//System.out.println("Head post loop: " + head);
}
return start;
}
Test output:
Original list: 3 1 2 3 3 5 3
Modified list: 1 2 5
struct LinkedList* deleteDuplicate(struct LinkedList *head, int data)
{
struct LinkedList *flag , *temp=head;
int i;
//delete duplicate data if start from first node
while( (head) && (head)->data == data)
{
temp = head;
head = temp->next;
if(temp)
{
temp->next = NULL;
free(temp);
}
}
// delete node if repeated data after the start node
while(temp)
{
flag = temp;
temp = temp->next;
if(temp && temp->data == data)
{
flag->next = temp->next;
temp->next = NULL;
free(temp);
temp = flag;
}
}
return head;
}
Java version:
public void delete(int value){
Node current = this.head;
Node prev = null;
if(current == null)
return;
while(current!=null){
if(current.getData() == value){
if(prev == null){
this.head = current.getNext();
current.setNext(null);
current = this.head;
}else{
prev.setNext(current.getNext());
current.setNext(null);
current = prev.getNext();
}
}
else{
prev = current;
current = current.getNext();
}
}
}
void deletecopies(struct listnode *head, int data)
{
struct listnode *current =head; temp =head;
while ( current)
{
if ( current->data == data)
{
if (current == head )
{
head = head->next;
free(current);
current = head;
}
else
{
temp->next = current->next;
free(current);
current = temp->next;
}
continue;
}
temp = current;
current = current->next;
}
}
- Martin August 17, 2012