问题是找到 2 个排序链表的交集并将公共元素存储在第三个列表中。
我的方法是使临时指针temp1，temp2分别初始化head1(列表 1 的负责人(和head2(列表 2 的负责人(。然后遍历两个列表并比较元素并相应地移动temp1和temp2。代码工作正常。
测试用例： 第一个链表=> 1->2->3->4->6 第二个链表是 2->4->6->8，然后函数应该创建并返回第三个列表为 2->4->6。
但我对时间复杂度是多少感到困惑：O(m+n(或O(min(m，n((？(m，n 是列表 1 和列表 2 中的元素数(。
我的代码：
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
void append(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so make next
of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
return;
}
struct Node* sortedIntersect(struct Node* head1,struct Node*head2)
{
struct Node*head3=NULL;
struct Node*temp1=head1;
struct Node*temp2=head2;
while(temp1!=NULL&&temp2!=NULL)
{
if(temp1->data<temp2->data)
{if(temp1->next!=NULL)
temp1=temp1->next;
else
break;
}
else if(temp1->data>temp2->data)
{
if(temp2->next!=NULL)
temp2=temp2->next;
else{
break;
}
}
else
{
append(&head3,temp1->data);
temp1=temp1->next;
temp2=temp2->next;
}
}
return head3;
}
/* Function to insert a node at the beginging 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;
}
}
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("n Linked list containing common items of a & b n ");
printList(intersect);
return 0;
}
这是一个可以在O(m+n)中解决的问题。
但是，此解决方案并不O(m+n)。在方法中添加的每个元素intersectSorted都使用方法append添加，该方法遍历整个当前输出列表。
所以时间复杂度是O((m+n)log(min(m,n))
就像在while的每次迭代中一样，至少有一个指针指向下一个指针，并且while终止的条件是没有指针到达终点，时间复杂度将O(min(m,n))。
在worst case中，它将O(m+n)
example: {1,3,5,7} {2,4,6,8}在这种情况下
，您遍历了 列表。
average情况下，它将是
O(min(m,n) + number of times you don't increment the smaller list)
example : {1,2,3,4,6} {2,4,6,8,9,10}
在这种情况下，您终止 到达第一行列表末尾但在您之间时的循环 递增第二个列表而不递增第一个列表。
best情况下，它将O(min(m,n))
example: {1,2,3} {1,2,3,4,}
在这种情况下，您将终止 到达第一个列表末尾后的循环。