给定两个按递增顺序排序的列表，创建并返回一个表示两个列表相交的新列表。新的清单应该用自己的记忆来制作——原来的清单不应该改变。
null
例子：
Input: First linked list: 1->2->3->4->6Second linked list be 2->4->6->8, Output: 2->4->6.The elements 2, 4, 6 are common in both the list so they appear in the intersection list. Input: First linked list: 1->2->3->4->5Second linked list be 2->3->4, Output: 2->3->4The elements 2, 3, 4 are common in both the list so they appear in the intersection list.
方法1 : 使用虚拟节点。 方法： 其想法是在结果列表的开头使用一个临时虚拟节点。指针尾部始终指向结果列表中的最后一个节点，因此可以轻松添加新节点。虚拟节点最初为尾部提供一个指向的内存空间。这个虚拟节点是有效的，因为它只是临时的，并且是在堆栈中分配的。循环继续，从“a”或“b”中移除一个节点，并将其添加到尾部。当遍历给定的列表时，结果为dummy。接下来，当值从虚拟对象的下一个节点分配时。如果两个元素相等，则移除两个元素并将其插入尾部。否则，删除两个列表中较小的元素。
以下是上述方法的实施情况：
C++
#include<bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; Node* next; }; void push(Node** head_ref, int new_data); /*This solution uses the temporary dummy to build up the result list */ Node* sortedIntersect(Node* a, Node* b) { Node dummy; Node* tail = &dummy; dummy.next = NULL; /* Once one or the other list runs out -- we're done */ while (a != NULL && b != NULL) { if (a->data == b->data) { push((&tail->next), a->data); tail = tail->next; a = a->next; b = b->next; } /* advance the smaller list */ else if (a->data < b->data) a = a->next; else b = b->next; } return (dummy.next); } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = (Node*) malloc ( sizeof (Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty lists */ Node* a = NULL; Node* b = NULL; Node* intersect = NULL; /* Let us create the first sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6 */ push(&a, 6); push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); /* Let us create the second sorted linked list Created linked list will be 2->4->6->8 */ push(&b, 8); push(&b, 6); push(&b, 4); push(&b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); cout<< "Linked list containing common items of a & b " ; printList(intersect); } |
C
#include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; void push( struct Node** head_ref, int new_data); /*This solution uses the temporary dummy to build up the result list */ struct Node* sortedIntersect( struct Node* a, struct Node* b) { struct Node dummy; struct Node* tail = &dummy; dummy.next = NULL; /* Once one or the other list runs out -- we're done */ while (a != NULL && b != NULL) { if (a->data == b->data) { push((&tail->next), a->data); tail = tail->next; a = a->next; b = b->next; } /* advance the smaller list */ else if (a->data < b->data) a = a->next; else b = b->next; } return (dummy.next); } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty lists */ struct Node* a = NULL; struct Node* b = NULL; struct Node* intersect = NULL; /* Let us create the first sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6 */ push(&a, 6); push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); /* Let us create the second sorted linked list Created linked list will be 2->4->6->8 */ push(&b, 8); push(&b, 6); push(&b, 4); push(&b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); printf ( " Linked list containing common items of a & b " ); printList(intersect); getchar (); } |
JAVA
class GFG { // head nodes for pointing to 1st and 2nd linked lists static Node a = null , b = null ; // dummy node for storing intersection static Node dummy = null ; // tail node for keeping track of // last node so that it makes easy for insertion static Node tail = null ; // class - Node static class Node { int data; Node next; Node( int data) { this .data = data; next = null ; } } // function for printing the list void printList(Node start) { Node p = start; while (p != null ) { System.out.print(p.data + " " ); p = p.next; } System.out.println(); } // inserting elements into list void push( int data) { Node temp = new Node(data); if (dummy == null ) { dummy = temp; tail = temp; } else { tail.next = temp; tail = temp; } } // function for finding intersection and adding it to dummy list void sortedIntersect() { // pointers for iterating Node p = a,q = b; while (p != null && q != null ) { if (p.data == q.data) { // add to dummy list push(p.data); p = p.next; q = q.next; } else if (p.data < q.data) p = p.next; else q= q.next; } } // Driver code public static void main(String args[]) { GFG list = new GFG(); // creating first linked list list.a = new Node( 1 ); list.a.next = new Node( 2 ); list.a.next.next = new Node( 3 ); list.a.next.next.next = new Node( 4 ); list.a.next.next.next.next = new Node( 6 ); // creating second linked list list.b = new Node( 2 ); list.b.next = new Node( 4 ); list.b.next.next = new Node( 6 ); list.b.next.next.next = new Node( 8 ); // function call for intersection list.sortedIntersect(); // print required intersection System.out.println( "Linked list containing common items of a & b" ); list.printList(dummy); } } // This code is contributed by Likhita AVL |
蟒蛇3
''' Link list node ''' class Node: def __init__( self ): self .data = 0 self . next = None '''This solution uses the temporary dummy to build up the result list ''' def sortedIntersect(a, b): dummy = Node() tail = dummy; dummy. next = None ; ''' Once one or the other list runs out -- we're done ''' while (a ! = None and b ! = None ): if (a.data = = b.data): tail. next = push((tail. next ), a.data); tail = tail. next ; a = a. next ; b = b. next ; # advance the smaller list elif (a.data < b.data): a = a. next ; else : b = b. next ; return (dummy. next ); ''' UTILITY FUNCTIONS ''' ''' Function to insert a node at the beginning of the linked list ''' def push(head_ref, new_data): ''' allocate node ''' new_node = Node() ''' put in the data ''' new_node.data = new_data; ''' link the old list off the new node ''' new_node. next = (head_ref); ''' move the head to point to the new node ''' (head_ref) = new_node; return head_ref ''' Function to print nodes in a given linked list ''' def printList(node): while (node ! = None ): print (node.data, end = ' ' ) node = node. next ; ''' Driver code''' if __name__ = = '__main__' : ''' Start with the empty lists ''' a = None ; b = None ; intersect = None ; ''' Let us create the first sorted linked list to test the functions Created linked list will be 1.2.3.4.5.6 ''' a = push(a, 6 ); a = push(a, 5 ); a = push(a, 4 ); a = push(a, 3 ); a = push(a, 2 ); a = push(a, 1 ); ''' Let us create the second sorted linked list Created linked list will be 2.4.6.8 ''' b = push(b, 8 ); b = push(b, 6 ); b = push(b, 4 ); b = push(b, 2 ); ''' Find the intersection two linked lists ''' intersect = sortedIntersect(a, b); print ( "Linked list containing common items of a & b " ); printList(intersect); # This code is contributed by rutvik_56. |
C#
using System; public class GFG { // dummy node for storing intersection static Node dummy = null ; // tail node for keeping track of // last node so that it makes easy for insertion static Node tail = null ; // class - Node public class Node { public int data; public Node next; public Node( int data) { this .data = data; next = null ; } } // head nodes for pointing to 1st and 2nd linked lists Node a = null , b = null ; // function for printing the list void printList(Node start) { Node p = start; while (p != null ) { Console.Write(p.data + " " ); p = p.next; } Console.WriteLine(); } // inserting elements into list void push( int data) { Node temp = new Node(data); if (dummy == null ) { dummy = temp; tail = temp; } else { tail.next = temp; tail = temp; } } // function for finding intersection and adding it to dummy list void sortedIntersect() { // pointers for iterating Node p = a,q = b; while (p != null && q != null ) { if (p.data == q.data) { // add to dummy list push(p.data); p = p.next; q = q.next; } else if (p.data < q.data) p = p.next; else q= q.next; } } // Driver code public static void Main(String []args) { GFG list = new GFG(); // creating first linked list list.a = new Node(1); list.a.next = new Node(2); list.a.next.next = new Node(3); list.a.next.next.next = new Node(4); list.a.next.next.next.next = new Node(6); // creating second linked list list.b = new Node(2); list.b.next = new Node(4); list.b.next.next = new Node(6); list.b.next.next.next = new Node(8); // function call for intersection list.sortedIntersect(); // print required intersection Console.WriteLine( "Linked list containing common items of a & b" ); list.printList(dummy); } } // This code is contributed by aashish1995 |
Javascript
<script> // head nodes for pointing to // 1st and 2nd linked lists var a = null , b = null ; // dummy node for storing intersection var dummy = null ; // tail node for keeping track of // last node so that it makes easy for insertion var tail = null ; // class - Node class Node { constructor(val) { this .data = val; this .next = null ; } } // function for printing the list function printList(start) { var p = start; while (p != null ) { document.write(p.data + " " ); p = p.next; } document.write(); } // inserting elements into list function push(data) { var temp = new Node(data); if (dummy == null ) { dummy = temp; tail = temp; } else { tail.next = temp; tail = temp; } } // function for finding intersection and // adding it to dummy list function sortedIntersect() { // pointers for iterating var p = a, q = b; while (p != null && q != null ) { if (p.data == q.data) { // add to dummy list push(p.data); p = p.next; q = q.next; } else if (p.data < q.data) p = p.next; else q = q.next; } } // Driver code // creating first linked list a = new Node(1); a.next = new Node(2); a.next.next = new Node(3); a.next.next.next = new Node(4); a.next.next.next.next = new Node(6); // creating second linked list b = new Node(2); b.next = new Node(4); b.next.next = new Node(6); b.next.next.next = new Node(8); // function call for intersection sortedIntersect(); // print required intersection document.write( "Linked list containing common items of a & b<br/>" ); printList(dummy); // This code is contributed by todaysgaurav </script> |
输出
Linked list containing common items of a & b 2 4 6
输出：
Linked list containing common items of a & b 2 4 6
复杂性分析：
- 时间复杂性： O（m+n），其中m和n分别是第一个和第二个链表中的节点数。 只需要遍历列表一次。
- 辅助空间： O（最小（m，n））。 输出列表最多可以存储min（m，n）个节点。
方法2 : 使用本地引用。 方法： 该解决方案在结构上与上述非常相似，但它避免使用虚拟节点，而是维护一个结构节点**指针lastprref，该指针始终指向结果列表的最后一个指针。这解决了与虚拟节点相同的情况，即在结果列表为空时处理结果列表。如果列表是在尾部构建的，则可以使用虚拟节点或结构节点**“引用”策略。
以下是上述方法的实施情况：
C
#include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; void push( struct Node** head_ref, int new_data); /* This solution uses the local reference */ struct Node* sortedIntersect( struct Node* a, struct Node* b) { struct Node* result = NULL; struct Node** lastPtrRef = &result; /* Advance comparing the first nodes in both lists. When one or the other list runs out, we're done. */ while (a != NULL && b != NULL) { if (a->data == b->data) { /* found a node for the intersection */ push(lastPtrRef, a->data); lastPtrRef = &((*lastPtrRef)->next); a = a->next; b = b->next; } else if (a->data < b->data) a = a->next; /* advance the smaller list */ else b = b->next; } return (result); } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty lists */ struct Node* a = NULL; struct Node* b = NULL; struct Node* intersect = NULL; /* Let us create the first sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6 */ push(&a, 6); push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); /* Let us create the second sorted linked list Created linked list will be 2->4->6->8 */ push(&b, 8); push(&b, 6); push(&b, 4); push(&b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); printf ( " Linked list containing common items of a & b " ); printList(intersect); getchar (); } |
输出
Linked list containing common items of a & b 2 4 6
输出：
Linked list containing common items of a & b 2 4 6
复杂性分析：
- 时间复杂性： O（m+n），其中m和n分别是第一个和第二个链表中的节点数。 只需要遍历列表一次。
- 辅助空间： O（最大（m，n））。 输出列表最多可以存储m+n个节点。
方法3 : 递归解。 方法： 递归方法与上述两种方法非常相似。构建一个递归函数，该函数接受两个节点并返回一个链表节点。比较两个列表的第一个元素。
- 如果它们相似，则使用两个列表的下一个节点调用递归函数。使用当前节点的数据创建一个节点，并将递归函数返回的节点放在所创建节点的下一个指针上。返回创建的节点。
- 如果值不相等，则删除两个列表中较小的节点，并调用递归函数。
以下是上述方法的实施情况：
C++
#include <bits/stdc++.h> using namespace std; // Link list node struct Node { int data; struct Node* next; }; struct Node* sortedIntersect( struct Node* a, struct Node* b) { // base case if (a == NULL || b == NULL) return NULL; /* If both lists are non-empty */ /* Advance the smaller list and call recursively */ if (a->data < b->data) return sortedIntersect(a->next, b); if (a->data > b->data) return sortedIntersect(a, b->next); // Below lines are executed only // when a->data == b->data struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node)); temp->data = a->data; // Advance both lists and call recursively temp->next = sortedIntersect(a->next, b->next); return temp; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ void push( struct Node** head_ref, int new_data) { /* Allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* Put in the data */ new_node->data = new_data; /* Link the old list off the new node */ new_node->next = (*head_ref); /* Move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList( struct Node* node) { while (node != NULL) { cout << " " << node->data; node = node->next; } } // Driver code int main() { /* Start with the empty lists */ struct Node* a = NULL; struct Node* b = NULL; struct Node* intersect = NULL; /* Let us create the first sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6 */ push(&a, 6); push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); /* Let us create the second sorted linked list Created linked list will be 2->4->6->8 */ push(&b, 8); push(&b, 6); push(&b, 4); push(&b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); cout << " Linked list containing " << "common items of a & b " ; printList(intersect); return 0; } // This code is contributed by shivanisinghss2110 |
C
#include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; struct Node* sortedIntersect( struct Node* a, struct Node* b) { /* base case */ if (a == NULL || b == NULL) return NULL; /* If both lists are non-empty */ /* advance the smaller list and call recursively */ if (a->data < b->data) return sortedIntersect(a->next, b); if (a->data > b->data) return sortedIntersect(a, b->next); // Below lines are executed only // when a->data == b->data struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node)); temp->data = a->data; /* advance both lists and call recursively */ temp->next = sortedIntersect(a->next, b->next); return temp; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty lists */ struct Node* a = NULL; struct Node* b = NULL; struct Node* intersect = NULL; /* Let us create the first sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6 */ push(&a, 6); push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); /* Let us create the second sorted linked list Created linked list will be 2->4->6->8 */ push(&b, 8); push(&b, 6); push(&b, 4); push(&b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); printf ( " Linked list containing common items of a & b " ); printList(intersect); return 0; } |
JAVA
import java.util.*; class GFG{ // Link list node static class Node { int data; Node next; }; static Node sortedIntersect(Node a, Node b) { // base case if (a == null || b == null ) return null ; /* If both lists are non-empty */ /* Advance the smaller list and call recursively */ if (a.data < b.data) return sortedIntersect(a.next, b); if (a.data > b.data) return sortedIntersect(a, b.next); // Below lines are executed only // when a.data == b.data Node temp = new Node(); temp.data = a.data; // Advance both lists and call recursively temp.next = sortedIntersect(a.next, b.next); return temp; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ static Node push(Node head_ref, int new_data) { /* Allocate node */ Node new_node = new Node(); /* Put in the data */ new_node.data = new_data; /* Link the old list off the new node */ new_node.next = head_ref; /* Move the head to point to the new node */ head_ref = new_node; return head_ref; } /* Function to print nodes in a given linked list */ static void printList(Node node) { while (node != null ) { System.out.print( " " + node.data); node = node.next; } } // Driver code public static void main(String[] args) { /* Start with the empty lists */ Node a = null ; Node b = null ; Node intersect = null ; /* Let us create the first sorted linked list to test the functions Created linked list will be 1.2.3.4.5.6 */ a = push(a, 6 ); a = push(a, 5 ); a = push(a, 4 ); a = push(a, 3 ); a = push(a, 2 ); a = push(a, 1 ); /* Let us create the second sorted linked list Created linked list will be 2.4.6.8 */ b = push(b, 8 ); b = push(b, 6 ); b = push(b, 4 ); b = push(b, 2 ); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); System.out.print( " Linked list containing " + "common items of a & b " ); printList(intersect); } } // This code is contributed by umadevi9616 |
C#
using System; public class GFG { // Link list node public class Node { public int data; public Node next; }; static Node sortedIntersect(Node a, Node b) { // base case if (a == null || b == null ) return null ; /* If both lists are non-empty */ /* * Advance the smaller list and call recursively */ if (a.data < b.data) return sortedIntersect(a.next, b); if (a.data > b.data) return sortedIntersect(a, b.next); // Below lines are executed only // when a.data == b.data Node temp = new Node(); temp.data = a.data; // Advance both lists and call recursively temp.next = sortedIntersect(a.next, b.next); return temp; } /* UTILITY FUNCTIONS */ /* * Function to insert a node at the beginning of the linked list */ static Node push(Node head_ref, int new_data) { /* Allocate node */ Node new_node = new Node(); /* Put in the data */ new_node.data = new_data; /* Link the old list off the new node */ new_node.next = head_ref; /* Move the head to point to the new node */ head_ref = new_node; return head_ref; } /* * Function to print nodes in a given linked list */ static void printList(Node node) { while (node != null ) { Console.Write( " " + node.data); node = node.next; } } // Driver code public static void Main(String[] args) { /* Start with the empty lists */ Node a = null ; Node b = null ; Node intersect = null ; /* * Let us create the first sorted linked list to test the functions Created * linked list will be 1.2.3.4.5.6 */ a = push(a, 6); a = push(a, 5); a = push(a, 4); a = push(a, 3); a = push(a, 2); a = push(a, 1); /* * Let us create the second sorted linked list Created linked list will be * 2.4.6.8 */ b = push(b, 8); b = push(b, 6); b = push(b, 4); b = push(b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); Console.Write( " Linked list containing " + "common items of a & b " ); printList(intersect); } } // This code is contributed by umadevi9616 |
Javascript
<script> // Link list node class Node { constructor(){ this .data = 0; this .next = null ; } } function sortedIntersect(a, b) { // base case if (a == null || b == null ) return null ; /* If both lists are non-empty */ /* * Advance the smaller list and call recursively */ if (a.data < b.data) return sortedIntersect(a.next, b); if (a.data > b.data) return sortedIntersect(a, b.next); // Below lines are executed only // when a.data == b.data var temp = new Node(); temp.data = a.data; // Advance both lists and call recursively temp.next = sortedIntersect(a.next, b.next); return temp; } /* UTILITY FUNCTIONS */ /* * Function to insert a node at the beginning of the linked list */ function push(head_ref , new_data) { /* Allocate node */ var new_node = new Node(); /* Put in the data */ new_node.data = new_data; /* Link the old list off the new node */ new_node.next = head_ref; /* Move the head to point to the new node */ head_ref = new_node; return head_ref; } /* * Function to print nodes in a given linked list */ function printList(node) { while (node != null ) { document.write( " " + node.data); node = node.next; } } // Driver code /* Start with the empty lists */ var a = null ; var b = null ; var intersect = null ; /* * Let us create the first sorted linked list to test the functions Created * linked list will be 1.2.3.4.5.6 */ a = push(a, 6); a = push(a, 5); a = push(a, 4); a = push(a, 3); a = push(a, 2); a = push(a, 1); /* * Let us create the second sorted linked list Created linked list will be * 2.4.6.8 */ b = push(b, 8); b = push(b, 6); b = push(b, 4); b = push(b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); document.write( " Linked list containing " + "common items of a & b <br/> " ); printList(intersect); // This code is contributed by Rajput-Ji </script> |
输出
Linked list containing common items of a & b 2 4 6
复杂性分析：
- 时间复杂性： O（m+n），其中m和n分别是第一个和第二个链表中的节点数。 只需要遍历列表一次。
- 辅助空间： O（最大（m，n））。 输出列表最多可以存储m+n个节点。
方法4： 使用散列
JAVA
import java.util.*; // This code is contributed by ayyuce demirbas public class LinkedList { Node head; static class Node { int data; Node next; Node( int d) { data = d; next= null ; } } public void printList() { Node n= head; while (n!= null ) { System.out.println(n.data+ " " ); n=n.next; } } public void append( int d) { Node n= new Node(d); if (head== null ) { head= new Node(d); return ; } n.next= null ; Node last= head; while (last.next != null ) { last=last.next; } last.next=n; return ; } static int [] intersection(Node tmp1, Node tmp2, int k) { int [] res = new int [k]; HashSet<Integer> set = new HashSet<Integer>(); while (tmp1 != null ) { set.add(tmp1.data); tmp1=tmp1.next; } int cnt= 0 ; while (tmp2 != null ) { if (set.contains(tmp2.data)) { res[cnt]=tmp2.data; cnt++; } tmp2=tmp2.next; } return res; } public static void main(String[] args) { LinkedList ll = new LinkedList(); LinkedList ll1 = new LinkedList(); ll.append( 0 ); ll.append( 1 ); ll.append( 2 ); ll.append( 3 ); ll.append( 4 ); ll.append( 5 ); ll.append( 6 ); ll.append( 7 ); ll1.append( 9 ); ll1.append( 0 ); ll1.append( 12 ); ll1.append( 3 ); ll1.append( 4 ); ll1.append( 5 ); ll1.append( 6 ); ll1.append( 7 ); int [] arr= intersection(ll.head, ll1.head, 6 ); for ( int i : arr) { System.out.println(i); } } } |
C#
using System; using System.Collections.Generic; // This code is contributed by ayyuce demirbas public class List { Node head; public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } public void printList() { Node n = head; while (n != null ) { Console.WriteLine(n.data + " " ); n = n.next; } } public void append( int d) { Node n = new Node(d); if (head == null ) { head = new Node(d); return ; } n.next = null ; Node last = head; while (last.next != null ) { last = last.next; } last.next = n; return ; } static int [] intersection(Node tmp1, Node tmp2, int k) { int [] res = new int [k]; HashSet< int > set = new HashSet< int >(); while (tmp1 != null ) { set .Add(tmp1.data); tmp1 = tmp1.next; } int cnt = 0; while (tmp2 != null ) { if ( set .Contains(tmp2.data)) { res[cnt] = tmp2.data; cnt++; } tmp2 = tmp2.next; } return res; } public static void Main(String[] args) { List ll = new List(); List ll1 = new List(); ll.append(0); ll.append(1); ll.append(2); ll.append(3); ll.append(4); ll.append(5); ll.append(6); ll.append(7); ll1.append(9); ll1.append(0); ll1.append(12); ll1.append(3); ll1.append(4); ll1.append(5); ll1.append(6); ll1.append(7); int [] arr = intersection(ll.head, ll1.head, 6); foreach ( int i in arr) { Console.WriteLine(i); } } } // This code is contributed by umadevi9616 |
输出
034567
复杂性分析：
- 时间复杂度：O（n）
如果您发现上述代码/算法不正确，请写下评论，或者找到更好的方法来解决相同的问题。 参考资料： 中央图书馆。斯坦福。edu/105/LinkedList问题。pdf
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
