假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,’loading’和’being’的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为 datanext ,请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在的结点位置p)。要求:
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度。
本题为简单难度的链表题,解决方法有...
用户登录可进行刷题及查看答案
本题为简单难度的链表题,解决方法有很多,思维有一定难度。
注意,每个链表都具有头结点,设其中str1和str2的长度分别为 n1 和 n2。
方法一:哈希表
判断两个链表是否相交,可以使用哈希集合存储链表结点。
首先遍历链表str1,并将链表str1中的每个包含关键字的结点加入哈希集合中。然后遍历链表 str2,对于遍历到的每个结点,判断该结点是否在哈希集合中:
如果当前结点不在哈希集合中,则继续遍历下一个结点;
如果当前结点在哈希集合中,则后面的结点都在哈希集合中,即从当前结点开始的所有结点都在两个链表的相交部分,因此在链表str2中遍历到的第一个在哈希集合中的结点就是两个链表相交的结点,返回该结点。
如果链表str2中的所有结点都不在哈希集合中,则两个链表不相交,返回NULL。
C代码如下(含测试用例):
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include "uthash.h"
-
- struct ListNode {
- int data;
- struct ListNode *next;
- };
-
- struct HashTable {
- struct ListNode *key;
- UT_hash_handle hh;
- };
-
- struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
- struct HashTable *hashTable = NULL;
- struct ListNode *temp = str1->next;
- while (temp != NULL) {
- struct HashTable *tmp;
- HASH_FIND(hh, hashTable, &temp, sizeof(struct HashTable *), tmp);
- if (tmp == NULL) {
- tmp = malloc(sizeof(struct HashTable));
- tmp->key = temp;
- HASH_ADD(hh, hashTable, key, sizeof(struct HashTable *), tmp);
- }
- temp = temp->next;
- }
- temp = str2->next;
- while (temp != NULL) {
- struct HashTable *tmp;
- HASH_FIND(hh, hashTable, &temp, sizeof(struct HashTable *), tmp);
- if (tmp != NULL) {
- return temp;
- }
- temp = temp->next;
- }
- return NULL;
- }
-
- struct ListNode** createTwoLinkedList(char *s1, char *s2) {
- int len1 = strlen(s1);
- int len2 = strlen(s2);
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail1 = head1;
- struct ListNode* intersection_node = NULL;
- int p1 = 0;
- while (p1 < len1) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s1[p1];
- node->next = NULL;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s2[p2];
- node->next = NULL;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- struct ListNode* hs[] = {head1, head2};
- return hs;
- }
-
- int main() {
- char *s1 = "loading";
- char *s2 = "being";
- struct ListNode** strs = createTwoLinkedList(s1, s2);
- struct ListNode* str1 = strs[0];
- struct ListNode* str2 = strs[1];
- struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != NULL) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
注:C语言没有提过哈希表,可以采用三方开源uthash。
C++代码如下(含测试用例):
- #include <iostream>
- #include <string>
- #include <unordered_set>
- #include <vector>
- using namespace std;
-
- struct ListNode {
- int data;
- ListNode *next;
- };
-
- ListNode *getIntersectionNode(ListNode *str1, ListNode *str2) {
- unordered_set<ListNode *> visited;
- ListNode *temp = str1->next;
- while (temp != nullptr) {
- visited.insert(temp);
- temp = temp->next;
- }
- temp = str2->next;
- while (temp != nullptr) {
- if (visited.count(temp)) {
- return temp;
- }
- temp = temp->next;
- }
- return nullptr;
- }
-
- vector<ListNode *> createTwoLinkedList(string s1, string s2) {
- int len1 = s1.length();
- int len2 = s2.length();
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- ListNode* head1 = new ListNode();
- ListNode* tail1 = head1;
- ListNode* intersection_node = nullptr;
- int p1 = 0;
- while (p1 < len1) {
- ListNode* node = new ListNode();
- node->data = s1[p1];
- node->next = nullptr;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- ListNode* head2 = new ListNode();
- ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- ListNode* node = new ListNode();
- node->data = s2[p2];
- node->next = nullptr;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- return vector<ListNode *>{head1, head2};
- }
-
- int main() {
- string s1 = "loading";
- string s2 = "being";
- vector<ListNode *> strs = createTwoLinkedList(s1, s2);
- ListNode* str1 = strs[0];
- ListNode* str2 = strs[1];
- ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != nullptr) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
-
复杂度分析
方法二:辅助栈
从后往前遍历两个链表,找到最后一个相同的结点。利用栈先进后出的性质,将两条链表分别压入两个栈中,然后循环比较两个栈的栈顶元素,同时记录上一位栈顶元素。当遇到第一个不同的结点时,结束循环,上一位栈顶元素即是答案。
C代码如下(含测试用例):
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- #define MAXSIZE 101
-
- struct ListNode {
- int data;
- struct ListNode *next;
- };
-
- struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
- struct ListNode *stk1[MAXSIZE], *stk2[MAXSIZE];
- int stk1_top = 0, stk2_top = 0;
- struct ListNode *p1 = str1->next, *p2 = str2->next;
- while (p1 != NULL) {
- stk1[stk1_top++] = p1;
- p1 = p1->next;
- }
- while (p2 != NULL) {
- stk2[stk2_top++] = p2;
- p2 = p2->next;
- }
- struct ListNode *ans = NULL;
- while (stk1_top && stk2_top) {
- if (stk1[--stk1_top] == stk2[--stk2_top]) {
- ans = stk1[stk1_top];
- } else {
- break;
- }
- }
- return ans;
- }
-
- struct ListNode** createTwoLinkedList(char *s1, char *s2) {
- int len1 = strlen(s1);
- int len2 = strlen(s2);
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail1 = head1;
- struct ListNode* intersection_node = NULL;
- int p1 = 0;
- while (p1 < len1) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s1[p1];
- node->next = NULL;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s2[p2];
- node->next = NULL;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- struct ListNode* hs[] = {head1, head2};
- return hs;
- }
-
- int main() {
- char *s1 = "loading";
- char *s2 = "being";
- struct ListNode** strs = createTwoLinkedList(s1, s2);
- struct ListNode* str1 = strs[0];
- struct ListNode* str2 = strs[1];
- struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != NULL) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
C++代码如下(含测试用例):
- #include <iostream>
- #include <string>
- #include <stack>
- #include <vector>
- using namespace std;
-
- struct ListNode {
- int data;
- ListNode *next;
- };
-
- ListNode *getIntersectionNode(ListNode *str1, ListNode *str2) {
- stack<ListNode *> s1, s2;
- for (ListNode *p = str1->next; p != nullptr; p = p->next) {
- s1.push(p);
- }
- for (ListNode *p = str2->next; p != nullptr; p = p->next) {
- s2.push(p);
- }
- ListNode *ans = nullptr;
- while (!s1.empty() && !s2.empty()) {
- if (s1.top() == s2.top()) {
- ans = s1.top();
- } else {
- break;
- }
- s1.pop();
- s2.pop();
- }
- return ans;
- }
-
- vector<ListNode *> createTwoLinkedList(string s1, string s2) {
- int len1 = s1.length();
- int len2 = s2.length();
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- ListNode* head1 = new ListNode();
- ListNode* tail1 = head1;
- ListNode* intersection_node = nullptr;
- int p1 = 0;
- while (p1 < len1) {
- ListNode* node = new ListNode();
- node->data = s1[p1];
- node->next = nullptr;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- ListNode* head2 = new ListNode();
- ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- ListNode* node = new ListNode();
- node->data = s2[p2];
- node->next = nullptr;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- return vector<ListNode *>{head1, head2};
- }
-
- int main() {
- string s1 = "loading";
- string s2 = "being";
- vector<ListNode *> strs = createTwoLinkedList(s1, s2);
- ListNode* str1 = strs[0];
- ListNode* str2 = strs[1];
- ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != nullptr) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
-
复杂度分析
方法三:双指针(差值法)
使用双指针的方法,可以将空间复杂度降至 O(1) 。
创建两个指针 p1和 p2 ,初始时分别指向str1和str2的头结点,分别遍历两条链表,得到链表长度分别为 l1 和 l2 (不考虑头结点),计算两条链表长度差值 |l1−l2| ,然后将指针 p1和 p2 重新分别指向str1和str2的头结点,长的链表的指针先的走过差值长度|l1−l2| ,然后两个指针 p1和 p2 同步遍历两条链表,当指针 p1 和 p2 指向同一个结点或者都为空时,返回它们指向的结点或者NULL。
C代码如下(含测试用例):
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- struct ListNode {
- int data;
- struct ListNode *next;
- };
-
- struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
- int l1 = 0;
- int l2 = 0;
- struct ListNode *p1 = str1->next, *p2 = str2->next;
- while (p1 != NULL) {
- l1++;
- p1 = p1->next;
- }
- while (p2 != NULL) {
- l2++;
- p2 = p2->next;
- }
- p1 = str1->next;
- p2 = str2->next;
- if (l1 > l2) {
- int d = l1 - l2;
- while (d > 0) {
- p1 = p1->next;
- d--;
- }
- } else if (l1 < l2) {
- int d = l2 - l1;
- while (d > 0) {
- p2 = p2->next;
- d--;
- }
- }
- while (p1 != p2) {
- p1 = p1->next;
- p2 = p2->next;
- }
- return p1;
- }
-
- struct ListNode** createTwoLinkedList(char *s1, char *s2) {
- int len1 = strlen(s1);
- int len2 = strlen(s2);
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail1 = head1;
- struct ListNode* intersection_node = NULL;
- int p1 = 0;
- while (p1 < len1) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s1[p1];
- node->next = NULL;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s2[p2];
- node->next = NULL;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- struct ListNode* hs[] = {head1, head2};
- return hs;
- }
-
- int main() {
- char *s1 = "loading";
- char *s2 = "being";
- struct ListNode** strs = createTwoLinkedList(s1, s2);
- struct ListNode* str1 = strs[0];
- struct ListNode* str2 = strs[1];
- struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != NULL) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
C++代码如下(含测试用例):
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
-
- struct ListNode {
- int data;
- ListNode *next;
- };
-
- ListNode* getIntersectionNode(ListNode* str1, ListNode* str2) {
- int l1 = 0;
- int l2 = 0;
- ListNode *p1 = str1->next, *p2 = str2->next;
- while (p1 != nullptr) {
- l1++;
- p1 = p1->next;
- }
- while (p2 != nullptr) {
- l2++;
- p2 = p2->next;
- }
- p1 = str1->next;
- p2 = str2->next;
- if (l1 > l2) {
- int d = l1 - l2;
- while (d > 0) {
- p1 = p1->next;
- d--;
- }
- } else if (l1 < l2) {
- int d = l2 - l1;
- while (d > 0) {
- p2 = p2->next;
- d--;
- }
- }
- while (p1 != p2) {
- p1 = p1->next;
- p2 = p2->next;
- }
- return p1;
- }
-
- vector<ListNode *> createTwoLinkedList(string s1, string s2) {
- int len1 = s1.length();
- int len2 = s2.length();
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- ListNode* head1 = new ListNode();
- ListNode* tail1 = head1;
- ListNode* intersection_node = nullptr;
- int p1 = 0;
- while (p1 < len1) {
- ListNode* node = new ListNode();
- node->data = s1[p1];
- node->next = nullptr;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- ListNode* head2 = new ListNode();
- ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- ListNode* node = new ListNode();
- node->data = s2[p2];
- node->next = nullptr;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- return vector<ListNode *>{head1, head2};
- }
-
- int main() {
- string s1 = "loading";
- string s2 = "being";
- vector<ListNode *> strs = createTwoLinkedList(s1, s2);
- ListNode* str1 = strs[0];
- ListNode* str2 = strs[1];
- ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != nullptr) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
-
复杂度分析
方法四:双指针(交替法)
方法二可以进一步改写,使得代码更加简洁,采用指针交替的方式省略差值的计算。
创建两个指针 p1和 p2 ,初始时分别指向str1和str2的第一个结点,然后将两个指针依次遍历两个链表的每个结点。具体做法如下:
每步操作需要同时更新指针 p1和 p2 。
当指针 p1 和 p2 指向同一个结点或者都为空时,返回它们指向的结点或者NULL。
思路证明:
情况一:两个链表相交
假设链表str1的不相交部分有 a 个结点,链表str2的不相交部分有 b 个结点,两个链表相交的部分有 c 个结点,则有 a+c=n1∧b+c=n2 。
情况二:两个链表不相交
C代码如下(含测试用例):
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- struct ListNode {
- int data;
- struct ListNode *next;
- };
-
- struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
- if (str1->next == NULL || str2->next == NULL) {
- return NULL;
- }
- struct ListNode *p1 = str1->next, *p2 = str2->next;
- while (p1 != p2) {
- p1 = p1 == NULL ? str2->next : p1->next;
- p2 = p2 == NULL ? str1->next : p2->next;
- }
- return p1;
- }
-
- struct ListNode** createTwoLinkedList(char *s1, char *s2) {
- int len1 = strlen(s1);
- int len2 = strlen(s2);
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail1 = head1;
- struct ListNode* intersection_node = NULL;
- int p1 = 0;
- while (p1 < len1) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s1[p1];
- node->next = NULL;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
- struct ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
- node->data = s2[p2];
- node->next = NULL;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- struct ListNode* hs[] = {head1, head2};
- return hs;
- }
-
- int main() {
- char *s1 = "loading";
- char *s2 = "being";
- struct ListNode** strs = createTwoLinkedList(s1, s2);
- struct ListNode* str1 = strs[0];
- struct ListNode* str2 = strs[1];
- struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != NULL) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
C++代码如下(含测试用例):
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
-
- struct ListNode {
- int data;
- ListNode *next;
- };
-
- ListNode *getIntersectionNode(ListNode *str1, ListNode *str2) {
- if (str1->next == nullptr || str2->next == nullptr) {
- return nullptr;
- }
- ListNode *p1 = str1->next, *p2 = str2->next;
- while (p1 != p2) {
- p1 = p1 == nullptr ? str2->next : p1->next;
- p2 = p2 == nullptr ? str1->next : p2->next;
- }
- return p1;
- }
-
- vector<ListNode *> createTwoLinkedList(string s1, string s2) {
- int len1 = s1.length();
- int len2 = s2.length();
- int suffix_len = 0;
- for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
- if (s1[i] == s2[j]) {
- suffix_len++;
- } else {
- break;
- }
- }
- ListNode* head1 = new ListNode();
- ListNode* tail1 = head1;
- ListNode* intersection_node = nullptr;
- int p1 = 0;
- while (p1 < len1) {
- ListNode* node = new ListNode();
- node->data = s1[p1];
- node->next = nullptr;
- tail1->next = node;
- tail1 = tail1->next;
- if (p1 == len1 - suffix_len) {
- intersection_node = node;
- }
- p1++;
-
- }
- ListNode* head2 = new ListNode();
- ListNode* tail2 = head2;
- int p2 = 0;
- while (p2 < len2) {
- ListNode* node = new ListNode();
- node->data = s2[p2];
- node->next = nullptr;
- tail2->next = node;
- tail2 = tail2->next;
- p2++;
- if (p2 == len2 - suffix_len) {
- node->next = intersection_node;
- break;
- }
- }
- return vector<ListNode *>{head1, head2};
- }
-
- int main() {
- string s1 = "loading";
- string s2 = "being";
- vector<ListNode *> strs = createTwoLinkedList(s1, s2);
- ListNode* str1 = strs[0];
- ListNode* str2 = strs[1];
- ListNode* intersectionNode = getIntersectionNode(str1, str2);
- if (intersectionNode != nullptr) {
- printf("%c", intersectionNode->data);
- }
- return 0;
- }
-
复杂度分析
登录后提交答案
暂无评论,来抢沙发