2012-408算法题

题目

IMG_20220604_204518.jpg

思想

p 指针指向 str1，q 指针指向 str2， 先让 p q 指针同一起点，及 p 、q 后的结点数量一样。
p、q 同步后移，当 p 结点、q 结点值第一次相等时用 f 指针记录
当 p 结点、q 结点值不相等时更新 f 指针
str1、str2 遍历完时，f 指针就指向要找的位置

代码

LNode* Find(LinkList str1, int len1, LinkList str2, int len2) {
    LNode *p = str1->next, *q = str2->next, *f = NULL;
    while(p != NULL && q != NULL) {
        if (len1 == len2) {
            if (p->data == q->data && f == NULL) 
                f = p;
            if (p->data != q->data) f = NULL;
            p = p->next;
            q = q->next;

        }
        else if (len1 > len2) {
            p = p->next;
            len1--;
        }
        else{
            q = q->next;
            len2--;
        }
    }
    return f;
}

测试

int main() {
    LinkList str1 = create('0');
    LNode *n1 = create('l');
    str1->next = n1;
    LNode *n2 = create('o');
    n1->next = n2;
    LNode *n3 = create('a');
    n2->next = n3;
    LNode *n4 = create('d');
    n3->next = n4;
    LNode *n5 = create('i');
    n4->next = n5;
    LNode *n6 = create('n');
    n5->next = n6;
    LNode *n7 = create('g');
    n6->next = n7;

    LinkList str2 = create('0');
    LNode *s1 = create('b');
    str2->next = s1;
    LNode *s2 = create('e');
    s1->next = s2;
    LNode *s3 = create('i');
    s2->next = s3;
    LNode *s4 = create('n');
    s3->next = s4;
    LNode *s5 = create('g');
    s4->next = s5;
    
    printf("result:%c\n", Find(str1, 7, str2, 5)->data);
    return 0;
}

捕获4.PNG

其他代码

#include<stdio.h>
#include<stdlib.h>


typedef struct node {
    char data;
    struct node *next;
}LNode, *LinkList;


LNode* create(char data) {
    LNode *n = (LNode *)malloc(sizeof(LNode));
    n->data = data;
    n->next = NULL;
    return n;
}