时间复杂度？

Question

问题是找到 2 个排序链表的交集并将公共元素存储在第三个链表中。

我的方法是制作临时指针 temp1 和 temp2 初始化为 head1 （列表 1 的头部）和 head2 （列表 2 的头部）respectively.And 然后遍历两个列表并比较元素并移动 temp1 和 temp2 accordingly.The 代码工作正常。

测试用例：第一个链表=> 1->2->3->4->6 第二个链表是 2->4->6->8，那么函数应该创建并且 return 第三个链表是 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;
}

Answer 1

与while的每次迭代一样，至少有一个指针指向下一个，while终止条件为none个指针到达终点，时间复杂度为 O(min(m,n)).

Answer 2

这是可以在O(m+n)中解决的问题。

但是，这个解决方案不是O(m+n)。你在方法 intersectSorted 中添加的每个元素都会用方法 append 添加，它遍历整个当前输出列表。

所以时间复杂度是O((m+n)log(min(m,n))

Answer 3

在worst case中它将是O(m+n)

example: {1,3,5,7} {2,4,6,8}
in this case you traverse both the list.

在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}
in this case you terminate the loop once you reach the end of first lined list but in between you increment the second list without increment the first list.

在best情况下它将是O(min(m,n))

example: {1,2,3} {1,2,3,4,}
in this case you will terminate the loop after reaching end of the first list.

时间复杂度？

Time Complexity?

c

linked-list

time-complexity

singly-linked-list