Write a C function that searches a given key ‘x’ in a given singly linked list. The function should return true if x is present in linked list and false otherwise.

   bool search(Node *head, int x)

For example, if the key to be searched is 15 and linked list is 14->21->11->30->10, then function should return false. If key to be searched is 14, then the function should return true.

Iterative Solution

2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
    a) current->key is equal to the key being searched return true.
    b) current = current->next
4) Return false

Java Programming:

[pastacode lang=”java” manual=”%2F%2F%20Iterative%20Java%20program%20to%20search%20an%20element%0A%2F%2F%20in%20linked%20list%0A%20%0A%2F%2FNode%20class%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20next%3B%0A%20%20%20%20Node(int%20d)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20next%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2FLinked%20list%20class%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2FHead%20of%20list%0A%20%0A%20%20%20%20%2F%2FInserts%20a%20new%20node%20at%20the%20front%20of%20the%20list%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2FAllocate%20new%20node%20and%20putting%20data%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FMake%20next%20of%20new%20node%20as%20head%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FMove%20the%20head%20to%20point%20to%20new%20Node%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2FChecks%20whether%20the%20value%20x%20is%20present%20in%20linked%20list%0A%20%20%20%20public%20boolean%20search(Node%20head%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20current%20%3D%20head%3B%20%20%20%20%2F%2FInitialize%20current%0A%20%20%20%20%20%20%20%20while%20(current%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(current.data%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%20%20%20%20%2F%2Fdata%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20false%3B%20%20%20%2F%2Fdata%20not%20found%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2FDriver%20function%20to%20test%20the%20above%20functions%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FStart%20with%20the%20empty%20list%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%20%20%20%2014-%3E21-%3E11-%3E30-%3E10%20%20*%2F%0A%20%20%20%20%20%20%20%20llist.push(10)%3B%0A%20%20%20%20%20%20%20%20llist.push(30)%3B%0A%20%20%20%20%20%20%20%20llist.push(11)%3B%0A%20%20%20%20%20%20%20%20llist.push(21)%3B%0A%20%20%20%20%20%20%20%20llist.push(14)%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(llist.search(llist.head%2C%2021))%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%20%20%20%7D%0A%7D%0A%2F%2F%20This%20code%20is%20contributed%20by%20Pratik%20Agarwal” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

Output:

Yes

Recursive Solution

bool search(head, x)
1) If head is NULL, return false.
2) If head's key is same as x, return true;
2) Else return search(head->next, x)

Java Programming:

[pastacode lang=”java” manual=”%2F%2F%20Recursive%20Java%20program%20to%20search%20an%20element%0A%2F%2F%20in%20linked%20list%0A%20%0A%20%0A%2F%2F%20Node%20class%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20next%3B%0A%20%20%20%20Node(int%20d)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20next%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Linked%20list%20class%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2FHead%20of%20list%0A%20%0A%20%20%20%20%2F%2FInserts%20a%20new%20node%20at%20the%20front%20of%20the%20list%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2FAllocate%20new%20node%20and%20putting%20data%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FMake%20next%20of%20new%20node%20as%20head%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FMove%20the%20head%20to%20point%20to%20new%20Node%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Checks%20whether%20the%20value%20x%20is%20present%0A%20%20%20%20%2F%2F%20in%20linked%20list%0A%20%20%20%20public%20boolean%20search(Node%20head%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20%20%20%20%20if%20(head%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20key%20is%20present%20in%20current%20node%2C%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20true%0A%20%20%20%20%20%20%20%20if%20(head.data%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20remaining%20list%0A%20%20%20%20%20%20%20%20return%20search(head.next%2C%20x)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20function%20to%20test%20the%20above%20functions%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Start%20with%20the%20empty%20list%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%20%20%20%20%20%20%2014-%3E21-%3E11-%3E30-%3E10%20%20*%2F%0A%20%20%20%20%20%20%20%20llist.push(10)%3B%0A%20%20%20%20%20%20%20%20llist.push(30)%3B%0A%20%20%20%20%20%20%20%20llist.push(11)%3B%0A%20%20%20%20%20%20%20%20llist.push(21)%3B%0A%20%20%20%20%20%20%20%20llist.push(14)%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(llist.search(llist.head%2C%2021))%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%20%20%20%7D%0A%7D%0A%2F%2F%20This%20code%20is%20contributed%20by%20Pratik%20Agarwal” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

Output:

Yes