جستجوی زیر لیست (Sublist Search) — راهنمای کاربردی

1// C++ program to find a list in second list 
2#include <bits/stdc++.h> 
3using namespace std; 
4  
5// A Linked List node 
6struct Node 
7{ 
8    int data; 
9    Node* next; 
10}; 
11  
12// Returns true if first list is present in second 
13// list 
14bool findList(Node* first, Node* second) 
15{ 
16    Node* ptr1 = first, *ptr2 = second; 
17  
18    // If both linked lists are empty, return true 
19    if (first == NULL && second == NULL) 
20        return true; 
21  
22    // Else If one is empty and other is not return 
23    // false 
24    if ( first == NULL || 
25        (first != NULL && second == NULL)) 
26        return false; 
27  
28    // Traverse the second list by picking nodes 
29    // one by one 
30    while (second != NULL) 
31    { 
32        // Initialize ptr2 with current node of second 
33        ptr2 = second; 
34  
35        // Start matching first list with second list 
36        while (ptr1 != NULL) 
37        { 
38            // If second list becomes empty and first 
39            // not then return false 
40            if (ptr2 == NULL) 
41                return false; 
42  
43            // If data part is same, go to next 
44            // of both lists 
45            else if (ptr1->data == ptr2->data) 
46            { 
47                ptr1 = ptr1->next; 
48                ptr2 = ptr2->next; 
49            } 
50  
51            // If not equal then  break the loop 
52            else break; 
53        } 
54  
55        // Return true if first list gets traversed 
56        // completely that means it is matched. 
57        if (ptr1 == NULL) 
58            return true; 
59  
60        // Initialize ptr1 with first again 
61        ptr1 = first; 
62  
63        // And go to next node of second list 
64        second = second->next; 
65    } 
66  
67    return false; 
68} 
69  
70/* Function to print nodes in a given linked list */
71void printList(Node* node) 
72{ 
73    while (node != NULL) 
74    { 
75        printf("%d ", node->data); 
76        node = node->next; 
77    } 
78} 
79  
80// Function to add new node to linked lists 
81Node *newNode(int key) 
82{ 
83    Node *temp = new Node; 
84    temp-> data= key; 
85    temp->next = NULL; 
86    return temp; 
87} 
88  
89/* Driver program to test above functions*/
90int main() 
91{ 
92    /* Let us create two linked lists to test 
93    the above functions. Created lists shall be 
94        a: 1->2->3->4 
95        b: 1->2->1->2->3->4*/
96    Node *a = newNode(1); 
97    a->next = newNode(2); 
98    a->next->next = newNode(3); 
99    a->next->next->next = newNode(4); 
100  
101    Node *b = newNode(1); 
102    b->next = newNode(2); 
103    b->next->next = newNode(1); 
104    b->next->next->next = newNode(2); 
105    b->next->next->next->next = newNode(3); 
106    b->next->next->next->next->next = newNode(4); 
107  
108    findList(a,b) ? cout << "LIST FOUND" : 
109                    cout << "LIST NOT FOUND"; 
110  
111    return 0; 
112}

1// Java program to find a list in second list 
2import java.util.*; 
3class GFG  
4{  
5  
6// A Linked List node 
7static class Node  
8{ 
9    int data; 
10    Node next; 
11}; 
12  
13// Returns true if first list is  
14// present in second list 
15static boolean findList(Node first, 
16                        Node second) 
17{ 
18    Node ptr1 = first, ptr2 = second; 
19  
20    // If both linked lists are empty, 
21    // return true 
22    if (first == null && second == null) 
23        return true; 
24  
25    // Else If one is empty and  
26    // other is not, return false 
27    if (first == null || 
28       (first != null && second == null)) 
29        return false; 
30  
31    // Traverse the second list by  
32    // picking nodes one by one 
33    while (second != null) 
34    { 
35        // Initialize ptr2 with  
36        // current node of second 
37        ptr2 = second; 
38  
39        // Start matching first list  
40        // with second list 
41        while (ptr1 != null) 
42        { 
43            // If second list becomes empty and  
44            // first not then return false 
45            if (ptr2 == null) 
46                return false; 
47  
48            // If data part is same, go to next 
49            // of both lists 
50            else if (ptr1.data == ptr2.data) 
51            { 
52                ptr1 = ptr1.next; 
53                ptr2 = ptr2.next; 
54            } 
55  
56            // If not equal then break the loop 
57            else break; 
58        } 
59  
60        // Return true if first list gets traversed 
61        // completely that means it is matched. 
62        if (ptr1 == null) 
63            return true; 
64  
65        // Initialize ptr1 with first again 
66        ptr1 = first; 
67  
68        // And go to next node of second list 
69        second = second.next; 
70    } 
71    return false; 
72} 
73  
74/* Function to print nodes in a given linked list */
75static void printList(Node node) 
76{ 
77    while (node != null) 
78    { 
79        System.out.printf("%d ", node.data); 
80        node = node.next; 
81    } 
82} 
83  
84// Function to add new node to linked lists 
85static Node newNode(int key) 
86{ 
87    Node temp = new Node(); 
88    temp.data= key; 
89    temp.next = null; 
90    return temp; 
91} 
92  
93// Driver Code 
94public static void main(String[] args)  
95{ 
96    /* Let us create two linked lists to test 
97    the above functions. Created lists shall be 
98        a: 1->2->3->4 
99        b: 1->2->1->2->3->4*/
100    Node a = newNode(1); 
101    a.next = newNode(2); 
102    a.next.next = newNode(3); 
103    a.next.next.next = newNode(4); 
104  
105    Node b = newNode(1); 
106    b.next = newNode(2); 
107    b.next.next = newNode(1); 
108    b.next.next.next = newNode(2); 
109    b.next.next.next.next = newNode(3); 
110    b.next.next.next.next.next = newNode(4); 
111  
112    if(findList(a, b) == true)  
113        System.out.println("LIST FOUND"); 
114    else
115        System.out.println("LIST NOT FOUND"); 
116} 
117} 
118  
119// This code is contributed by Princi Singh 

1// C# program to find a list in second list 
2using System; 
3  
4class GFG  
5{  
6  
7// A Linked List node 
8class Node  
9{ 
10    public int data; 
11    public Node next; 
12}; 
13  
14// Returns true if first list is  
15// present in second list 
16static Boolean findList(Node first, 
17                        Node second) 
18{ 
19    Node ptr1 = first, ptr2 = second; 
20  
21    // If both linked lists are empty, 
22    // return true 
23    if (first == null && second == null) 
24        return true; 
25  
26    // Else If one is empty and  
27    // other is not, return false 
28    if (first == null || 
29       (first != null && second == null)) 
30        return false; 
31  
32    // Traverse the second list by  
33    // picking nodes one by one 
34    while (second != null) 
35    { 
36        // Initialize ptr2 with  
37        // current node of second 
38        ptr2 = second; 
39  
40        // Start matching first list  
41        // with second list 
42        while (ptr1 != null) 
43        { 
44            // If second list becomes empty and  
45            // first not then return false 
46            if (ptr2 == null) 
47                return false; 
48  
49            // If data part is same, go to next 
50            // of both lists 
51            else if (ptr1.data == ptr2.data) 
52            { 
53                ptr1 = ptr1.next; 
54                ptr2 = ptr2.next; 
55            } 
56  
57            // If not equal then break the loop 
58            else break; 
59        } 
60  
61        // Return true if first list gets traversed 
62        // completely that means it is matched. 
63        if (ptr1 == null) 
64            return true; 
65  
66        // Initialize ptr1 with first again 
67        ptr1 = first; 
68  
69        // And go to next node of second list 
70        second = second.next; 
71    } 
72    return false; 
73} 
74  
75/* Function to print nodes 
76in a given linked list */
77static void printList(Node node) 
78{ 
79    while (node != null) 
80    { 
81        Console.Write("{0} ", node.data); 
82        node = node.next; 
83    } 
84} 
85  
86// Function to add new node to linked lists 
87static Node newNode(int key) 
88{ 
89    Node temp = new Node(); 
90    temp.data= key; 
91    temp.next = null; 
92    return temp; 
93} 
94  
95// Driver Code 
96public static void Main(String[] args)  
97{ 
98    /* Let us create two linked lists to test 
99    the above functions. Created lists shall be 
100        a: 1->2->3->4 
101        b: 1->2->1->2->3->4*/
102    Node a = newNode(1); 
103    a.next = newNode(2); 
104    a.next.next = newNode(3); 
105    a.next.next.next = newNode(4); 
106  
107    Node b = newNode(1); 
108    b.next = newNode(2); 
109    b.next.next = newNode(1); 
110    b.next.next.next = newNode(2); 
111    b.next.next.next.next = newNode(3); 
112    b.next.next.next.next.next = newNode(4); 
113  
114    if(findList(a, b) == true)  
115        Console.Write("LIST FOUND"); 
116    else
117        Console.Write("LIST NOT FOUND"); 
118} 
119} 
120  
121// This code is contributed by Rajput-Ji