链表Linked List-Search an element in a Linked List (Iterative and Recursive) （4）

小灰灰 2023-09-24 19:40 94阅读 0赞

# 1.Question #

Given a linked list and a key ‘X‘ in, the task is to check if X is present in the linked list or not.

> Input: 14->21->11->30->10, X = 14  
> Output: Yes  
> Explanation: 14 is present in the linked list.

> Input: 6->21->17->30->10->8, X = 13  
> Output: No

# 2.Methods #

## 1）Search an element in a Linked List (`Iterative Approach`): ##

`Time Complexity`: `O(N)`, Where N is the number of nodes in the LinkedList  
`Auxiliary Space`: `O(1)`

### Steps ###

1.  Initialize a node pointer, current = head.
2.  Do following while current is not NULL
    
     *  If the current value (i.e., current->key) is equal to the key being searched return true.
     *  Otherwise, move to the next node (current = current->next).
3.  If the key is not found, return false

class LinkedList {
        
        static ListNode head;
    
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
    
        public boolean search(ListNode head, int x) {
        
            ListNode current = head;
            while (current != null) {
        
                if (current.val == x) {
        
                    return true;
                }
                current = current.next;
            }
            return false;
        }
    
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(10);
            list.push(30);
            list.push(25);
            list.push(2);
            if (list.search(list.head, 2)) {
        
                System.out.println("yes");
            } else {
        
                System.out.println("no");
            }
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

yes

## 2）Search an element in a Linked List (`Recursive Approach`): ##

`Time Complexity`: `O(N)`  
`Auxiliary Space`: `O(N)`, Stack space used by recursive calls

### Steps ###

1.  If the head is NULL, return false.
2.  If the head’s key is the same as X, return true; Else recursively search in the next node.

class LinkedList {
        
        static Node head;
        public static void push(int new_data){
        
            Node new_node = new Node(new_data);
            new_node.next=head;
            head=new_node;
        }
        public boolean search(Node head,int x){
        
            if(head==null){
        
                return false;
            }
            if(head.val==x){
        
                return true;
            }
            return search(head.next,x);
        }
    
        public static void main(String[] args) {
        
            LinkedList list = new LinkedList();
            list.push(10);
            list.push(30);
            list.push(25);
            list.push(2);
            if(list.search(list.head,2)){
        
                System.out.println("yes");
            }else{
        
                System.out.println("no");
            }
        }
        static class Node {
        
    
            int val;
            Node next;
    
            Node(int d) {
        
                val = d;
                next = null;
            }
        }
    }

yes