假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading" 和 “being” 的存储映像如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 | data | next |，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在的结点位置 p）。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度。

链表

[tag_link]

顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另 一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第 一个公共结点。算法的基本设计思想：①分别求出 strl 和 str2 所指的两个链表的长度 m 和 n。②将两个链表以表尾对齐：令指针 p、q 分别指向 strl 和 str2 的头结点，若m≥n，则使 p 指向链表中的第 m-n+1 个结点；若m<n，则使 q 指向链表中的第 n-m+1 个结点，即使指针 p 和 q 所指的结点到表尾的长度相等。③反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。

2）算法的 C 语言代码描述：

struct Node {
  int data;
  Node *next;
};

int getLength(Node *h) {
  int length = 0;
  Node *p = h->next;
  while (p) {
    length++;
    p = p->next;
  }
  return length;
}

Node *findCommonSuffix(Node *h1, Node *h2) {
  Node *p1 = h1;
  Node *p2 = h2;
  int m = getLength(h1);
  int n = getLength(h2);
  if (m > n) {
    for (int i = 0; i < m-n; i++) {
      p1 = p1->next;
    }
  } else {
    for (int i = 0; i < n-m; i++) {
      p2 = p2->next;
    }
  }
  while (p1 != p2) {
    p1 = p1->next;
    p2 = p2->next;
  }
  return p1;
}

【评分说明】 ① 若考生所给算法实现正确，且时间复杂度为 O(m+n)，可给 12分；若算法正确，但时间复杂度超过 O(m+n)，则最高可给 9 分。② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。③ 时间复杂度为 O(len1+len2）或 O(max(len1,len2)), 其中 len1、len2 分别为两个链表的长度。