2.1 线性表

线性表

是具有相同数据类型的n个元素的有限序列。有前驱和后继。

是一种逻辑结构。

根据不同的存储方式，分为：

  • 顺序存储→顺序表
  • 链式存储→单链表，双链表，循环链表，静态链表

线性表的基本操作

初始化表，InitList(&L) 初始化表，构造一个空的线性表。

求表长，Length(L) 返回线性表L的长度，即L中数据元素的个数。

按位（键位）查找操作，GetElem(L,i) 获取表中第i个位置的元素的值。

按值(关键字）查找操作，LocateElem(L,e) 获取表L中查找具有给定值e的元素。

插入操作，ListInsert(&L,i,e) 在表L中的第i个位置上，插入指定元素e。

删除操作，ListDelete(&L,i,&e) 删除表L中第i个位置的元素，并用e返回删除元素的值。

只需要读取L → 用L（传值）

需要修改L本身 → 用&L（传地址）

2.2 线性表的顺序表示

顺序表

线性表的顺序存储，叫顺序表。

优点：①随机存取（适合用数组来描述）。②存储密度高。

缺点：①插入和删除麻烦（插入要移动n/2个元素，删除要移动(n-1)/2个元素）。②存储需要分配连续空间。

sizeof(ElemType)：每个数据元素所占用存储空间的大小

数组的下标【即索引】从0开始。

线性表的下标【即位置】从1开始。

基本操作

1.顺序表的初始化

1
2
3
4
5
6
7
8
9
10
11
// SqList L;	// 声明一个顺序表
// 静态初始化
void InitList(SqList &L){
    L.length = 0;	//顺序表初始长度为0
}
// 动态初始化 
void InitList(SeqList &L){
    L.data = (ElemType *)malloc(InitSize*sizeof(ElemType));	//分配存储空间？
    L.length = 0;	
    L.MaxSize = InitSize;	//初始存储容量
}

2.插入操作

在顺序表L的第i个位置插入新元素e（1≤i≤L.length+1）。

位置是从1开始的，索引是从0开始的。

length是长度，数值上=位置最大值，或=索引+1。

最好时间复杂度：O1

最坏时间复杂度：On

平均时间复杂度：On（平均移动次数n/2）

1
2
3
4
5
6
7
8
9
10
11
bool ListInsert {SqList &L,int i,ElemType e}{
    if (i<1 || i>L.length+1)
        return false;
    if(L.length >= MaxSize) //if存满了
        return false;
    for(int j=L.length;j>=i;j--) //后移i位置之后的元素
        L.data[j]=L.data[j-1];
    L.data[i-1] = e;
    L.length++;
    return false;
}

3.删除操作

删除顺序表L第i个位置（索引i-1⭐）的元素，用引用变量e返回。

最好时间复杂度：O1

最坏时间复杂度：On

平均时间复杂度：On（平均移动次数n-1 /2）

1
2
3
4
5
6
7
8
9
bool ListDelete(SqList &L,int i,ElemType &e){
    if(i<1 || i>L.length)
        return false;
    e=L.data[i-1];	//将被删除的元素赋给e
    for(int j=i;j<L.length;j++)
        L.data[j-1] = L.data[j];	//将第i个位置后的元素往前移
    L.length--;	//线性表长度减一
    return true;
}

4.按值查找

在顺序表L中查找第一个元素等于e的元素，并返回其位序。

最好时间复杂度：O1

最坏时间复杂度：On

平均时间复杂度：On（平均比较次数n+1 /2）

1
2
3
4
5
6
7
int LocalElem(SqList L,ElemType e){
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

大题部分

10. 【2010 统考真题】
设将 $n$（$n > 1$）个整数按序放到一维数组 $R$ 中。设计一个在时间和空间两方面都尽可能高效的算法，将 $R$ 中保存的序列循环左移 $p$（$0 < p < n$）个位置，即将 $R$ 中的数据由
$$
(X_0, X_1, \cdots, X_{n-1})
$$
变换为
$$
(X_p, X_{p+1}, \cdots, X_{n-1}, X_0, X_1, \cdots, X_{p-1}).
$$
要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 1.算法思想：三次逆置，前面部分逆置，后面部分逆置，整体再逆置;
// 将问题视为把数组ab转成数组ba（a代表数组的前p个元素，b代表数组剩下的后n-p个元素）。先将a逆置得到a﹣¹b，再将b逆置得到a﹣¹b﹣¹，最后逆置整个a﹣¹b﹣¹得到ba。

// 2.算法呈现，见下;
// 逆置函数，将R中【left,right】范围内的元素（由外向里逐个）反转
void reverse(int R,int left,int right){
    int temp;
    while(left<right){
        temp = R[left];
        R[left] = R[right];
        R[left] = temp;
        left++; //
        right--; //
    }
}

// 循环左移p位
void rotateLeft(int R[],int n,int p){
    p = p % n;	//防止p大于n，取余数；
    if(p==0)
        return;
    reverse(R,0,p-1);	//第一步：逆置前p个元素；
    reverse(R,p,n-1);	//第二步：逆置剩余n-p个元素；
    reverse(R,0,n-1);	//第一步：整体逆置
}

//3.三个reverse函数的时间复杂度分别为：O（p/2），O（n-p/2）,O（n/2）
//所以总的时间复杂度：O（n），空间复杂度O（1）;

11. 【2011 统考真题】
一个长度为 $L$（$L \geq 1$）的升序序列 $S$，处在第 $\lfloor L/2 \rfloor$ 个位置的数称为 $S$ 的中位数。例如，若序列
$$
S_1 = (11, 13, 15, 17, 19)
$$
则 $S_1$ 的中位数是 15。两个序列的中位数是它们所有元素的升序序列的中位数。例如，若
$$
S_2 = (2, 4, 6, 8, 20)
$$
则 $S_1$ 和 $S_2$ 的中位数是 11。现在有两个等长升序序列 $A$ 和 $B$，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 $A$ 和 $B$​ 的中位数。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 1.算法思想：
// way1：先合并两个序列A、B。再对序列进行排序。最后再找出中位数。（pass，不够高效）
// way2：不断舍弃不可能包含中位数的部分。
// 具体实现：
// 	①分别求A和B的中位数a_mid,b_mid。
// 	②比较A和B的中位数。若a_mid==b_mid则它就是合并后的中位数。若a_mid>b_mid则中位数在A的右半部份和B的左半部分之间。若a_mid<b_mid则中位数在A的左半部分和B的右半部分之间。
// 	③舍弃不可能的一半，重复第①步！
//	④当两个系列都只剩一个元素时，较小的那个就是中位数


// 2.算法实现
int findMedian(int A[],int B[],int n){
    int a_left = 0 , a_right = n-1;
    int b_left = 0 , b_right = n-1;
    
    while(a_left<a_right){
        int a_mid = (a_left+a_right)/2;
        int b_mid = (b_left+b_right)/2;
        
        if(A[a_mid]==B[b_mid])
            return A[a_mid];
        
        if((a_right-a_left+1)%2 == 1){	//如果区间长度为奇数
            if(A[a_mid]<B[b_mid]){
                a_left = a_mid;
                b_right = b_mid;
            }else{
                a_right = a_mid;
                b_left = b_mid;
            }
        }
        else{	//如果区间长度为偶数
            if(A[a_mid]<B[b_mid]){
                a_left = a_mid +1;
                b_right = b_mid;
            }else{
                a_right = a_mid;
                b_left = b_mid +1;
            }
        }
    }
    
    if (A[a_left] < B[b_left]){	//		算法结束时，A和B都只剩一个元素，返回较小的那一个元素
        return A[a_left];
    }else{
        return B[b_left]
    }
}


// 3.
// 时间复杂度：O（logn）【每次比较后，两个序列的长度都减半】
// 空间复杂度O（1）【只使用了常数个辅助变量】

12. 【2013 统考真题】
已知一个整数序列
$$
A = (a_0, a_1, \cdots, a_{n-1})
$$
其中 $0 \leq a_i < n$（$0 \leq i < n$），若存在
$$
a_{p_1} = a_{p_2} = \cdots = a_{p_m} = x
$$
且 $m > n/2$（$0 \leq p_k < n, 1 \leq k \leq m$），则称 $x$ 为 $A$ 的主元素。例如
$$
A = (0, 5, 5, 3, 5, 7, 5, 5)
$$
则 5 为主元素；又如
$$
A = (0, 5, 5, 3, 5, 1, 5, 7)
$$
则 $A$ 中没有主元素。假设 $A$ 中的 $n$ 个元素存储在一个一维数组中，请设计一个尽可能高效的算法，找出 $A$​ 的主元素。若存在主元素，则输出该元素；否则输出 -1。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 1.算法思想：
// way1：①先统计A序列中出现的不同元素的出现次数。②然后依据出现次数从大到小排序。③最后按顺序查看，如果有某个元素出现次数＞n/2，则为主元素。（pass）
// way2：利用值域开辟辅助数组，不需要排序。


// 2.具体实现
int Majority(int A[],int n){
    
    // ①申请一个大小为n的整型数组count，并全部初始化为0。
    int *count = (int*)calloc(n,sizeof(int));
    if(count == NULL) return -1;
    
    // ②遍历原始数组A，对于每个元素A[i]，执行count[A[i]]++。
    for(int i=0;i<n;i++){
        count[A[i]]++;	//
    }
    // ③遍历count数组，如果发现某个下标i对应的count[i]>n/2，则返回i。
    for(int i=0;i<n;i++){
        if(count[i]>n/2){	//
            free(count);
            return i;
        }
    }
    // ④如果遍历完都没找到，返回-1。
    free(count);
    return -1;	//没有主元素
}


// 3.
// 时间复杂度：O(n)【遍历两次数组，每次都是On】
// 空间复杂度：O(n)【值域限制在n之内，辅助数组长度为n】

13. 【2018 统考真题】
给定一个含 $n$（$n \geq 1$）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组
$$
{-5, 3, 2, 3}
$$
中未出现的最小正整数是 1；数组
$$
{1, 2, 3}
$$
中未出现的最小正整数是 4。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 1.算法思想：
//way1：①建立一个大小为n的辅助数组B[n]，数组的内容为空。②按顺序遍历原始数组A，对其值m=A[i]在辅助数组中对应的B[m]加1。③遍历完原始数组后，按顺序找到辅助数组第一个值为1的B[m],④m+1即为未出现过的最小正整数。（pass）
//way2：①建立一个大小为n的辅助数组B[n]，数组的内容为空。②遍历原始数组A，如果1≤A[i]≤n，令B[A[i]-1]=1【因为数组下标是从0开始的！】③遍历完原始数组后，按顺序找到辅助数组第一个值为0的索引i，则缺失的最小正整数是i+1。④特殊处理：如果辅助数组全是1，说明1-n都在，结果就是n+1。

// 2.具体实现：
# include <stdlib.h>
# include <stdio.h>
int findMissMin(int A[],int n){
    int *B = (int*)calloc(n,sizeof(int));
    
    for(int i=0;i<n;i++){
        if(A[i]>=1 && A[i]<=n){
            B[A[i]-1] = 1;
        }
    }
    
    for(int i=0;i<n;i++){
        if(B[i]==0){
            free(B);
            return i+1;
        }
    }
    
    free(B);
    return n+1;
}

// 3.
// 时间复杂度O(n)【数组A遍历一次，B遍历一次】
// 空间复杂度O(n)

14. 【2020 统考真题】
定义三元组 $(a, b, c)$（$a, b, c$ 均为整数）的距离为
$$
D = |a - b| + |b - c| + |c - a|.
$$
给定 3 个非空整数集合 $S_1, S_2$ 和 $S_3$，按升序排列存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a, b, c)$（$a \in S_1, b \in S_2, c \in S_3$）中的最小距离。例如
$$
S_1 = {1, 0, 9},\quad S_2 = {25, -10, 10, 11},\quad S_3 = {2, 9, 17, 30, 41}
$$
则最小距离为 2，相应的三元组为 $(9, 10, 9)$。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 语言或 C++ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 1.算法思想：对于上面的公式，实际上等于三个数中最大值与最小值的差的两倍。
// ①初始化：设置三个指针（下标），ijk分别指向数组S1S2S3的第一个元素（下标为0）
// ②迭代计算：在指针不越界的情况下，计算当前指向的三个元素构成的D值，并更新当前的最小距离minD。
// ③移动指针（贪心策略）为了找出更小的距离，我们需要让三个数尽可能地靠近。每次只移动当前指向元素最小的那个数组的指针⭐。
// ④重复②③，直到某一个数组遍历完毕。

// 2.实现过程

//辅助函数，返回三个数中的最小值
int minOfThree(int x,int y,int z){
    if(x<=y&&x<=z) return x;
    if(y<=x&&y<=z) return y;
    return z;
}
// 核心算法（假设S1,S2,S3是已排序的数组，n1n2n3是长度）
int findMinDistance(int S1[],int n1,int S2[],int n2,int S3[],int n3){
    int i = 0,j = 0,k = 0;
    int minD = 0x7fffffff; //初始化为一个足够大的数。
    
    // 三个数组都为遍历完时循环
    while(i<n1 && j<n2 && k<n3){
        int a = S1[i], b = S2[j], c = S3[k];
        int currentD = abs(a-b) + abs(b-c) + abs(c-a);
        
        if(currentD <minD){
            minD = currentD;	//更新最小距离
        }
        
        // 移动指向最小元素的指针
        int minVal = minOfThree(a,b,c);
        if(minVal==a) i++;
        else if(minVal==b) j++;
        else k++;
    }
    
    return minD;
}

2.3 线性表的链式表示

单链表

线性表的链式存储，也称单链表。

对于每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

| data | next | ：data为数据域，存放数据元素。next为指针域，存放后继节点的地址。

缺点：是非随机存储的存储结构，需要依次查找。

通常来说，用一个头指针L（或head）来标识一个单链表，指出链表的起始地址。

表尾节点的指针域为NULL（用^表示）。头指针为NULL时表示一个空表。

头节点：单链表第一个数据节点之前可以增加一个头节点（Optional）

  • 好处：①可以使在链表第一个位置上的操作和别的无不同。②无论链表是否为空，头指针都是指向头节点的，是非空指针。

image-20260811153350587

基本操作

1.单链表的初始化

带头节点的单链表的初始化：创造一个头节点，并让头指针指向头节点，头节点的next域初始化为NULL

1
2
3
4
5
bool InitList(LinkList &L){
    L = (LNode*)malloc(sizeof(LNode));	//创建头节点
    L->next = NULL;	//之后没有数据，L的指向的节点指针域为空
    return true;
}

不带头节点的单链表的初始化：只需将头指针L初始化为NULL

1
2
3
bool InitList(LinkList &L){
    L = NULL;	//之后没有数据，L指向的节点的数据域为空   
}

2.求表长（带头节点版本）

计算单链表中数据结点的个数

表长不包括头节点长度的。

时间复杂度：On

1
2
3
4
5
6
7
8
9
int Length(LinkList L){
    int len = 0;
    LNode *p = L;	//新指针p指向指针L所指向的同一个结点
    while (p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

不带头节点的实现

1
2
3
4
5
6
7
8
9
int Length(LinkList L){
    int len = 0;
    LNode *p = L;  // p指向第一个结点（也可能是NULL）
    while (p != NULL){  // 空链表时p=NULL，直接跳过循环
        len++;
        p = p->next;
    }
    return len;
}

3.按序号查找结点

寻找第i个结点，返回该节点的指针。

1
2
3
4
5
6
7
8
9
LNode *GetElem(LinkList L,int i){
    LNode *p = L;
    int j = 0;
    while(p != Null && j<i){
        p = p->next;
        j++;
    }
    return p;
}

4.按值查找表结点

若某结点的data域等于给定值e，返回该节点的指针。

时间复杂度为：On

1
2
3
4
5
6
LNode *LocateElem(LinkList L,ElemType e){
    LNode *p = L;
    while(p!=Null && P->data!=e)
        p = p->next;
    return p;
}

5.插入结点操作

将值为x的新节点插入到单链表的第i个位置。（后插：找到待插入位置的前驱，即第i-1个结点，再在其后插入）

时间复杂度：On

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ListInsert(LinkList &L,int i,ElemType e){
    //
    LNode *p = L;	//指针p指向当前扫描到的结点。
    int j =0;
    while(p!=NULL && j<i-1){	//循环直到找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p==NULL)	//i值不合法
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode)); //指针声明时带 *，使用时不带 *
    s ->data = e;
    s ->next = p->next;
    p->next = s;
    return true;
}

交换两个已存在结点的位置

1
2
3
4
5
6
// 先把s移动到p后面，再交换数据
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;

真正的交换指针

1
2
3
4
5
6
7
// 找到p的前驱prev_p和s的前驱prev_s
prev_p->next = s;
prev_s->next = p;
LNode *temp = p->next;
p->next = s->next;
s->next = temp;
// 不需要交换数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
初始状态：
[甲] → [乙] → [丙] → [丁] → [戊]
        ↑              ↑
        p              s

① prev_p->next = s：
[甲] ──→ [丁] → [戊]
  ↓
 [乙] → [丙]

② prev_s->next = p：
[甲] → [丁] → [戊]
  ↓
 [乙] ← [丙]

③ temp = p->next (temp=丙)：
[甲] → [丁] → [戊]
  ↓
 [乙] ← [丙]  (temp记录丙)

④ p->next = s->next (乙→戊)：
[甲] → [丁] → [戊]
  ↓        ↑
 [乙] ─────┘
  ↓
 [丙]  (temp)

⑤ s->next = temp (丁→丙)：
[甲] → [丁] → [丙] → [乙] → [戊]
        ↑              ↑
        s              p

6.删除结点操作

将单链表的第i个结点删除。【查找表中第i-1个结点（即被删结点的前驱，时期连接到第i+1个结点，再删除第i个结点】

时间复杂度：On

image-20260811203244291

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ListDelete(LinkList &L,int i,ElemType &e){
    // *p是被删结点的前驱
    LNode *p = L;
    int j=0;
    while(p->next!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p->next==NULL || j>i-1)
        return false;
    LNode *q = p->next;	//令q指向被删除结点
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

7.采用头插法建立单链表

将新节点插入到当前链表的表头，即头节点之后

image-20260811203306472

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList List_HeadInsert(LinkList &L){
    LNode *s;int x;
    L = (LNode*)malloc(sizeof(LNode));	//创建头节点
    L->next = NULL;
    scanf("%d",&x);	//输入结点的值
    while(x!=9999){
        ///输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x)；
    }
    return L;
}

如果单链表不带头节点，则上述代码中哪些地方需要修改？→主要修改的地方：因为在头部插入了新节点，每次插入新节点后，都需要将它的地址赋值给头指针L。

双链表

单链表结点只有一个指向后继的指针，所以只能从前往后遍历，要访问某个结点的前驱（插入，删除操作时），只能从头开始遍历。On

双链表，有两个指针prior和next。表头结点的prior域和尾结点next域都是NULL（^)

优点：在插入和删除操作上，比单链表快，O1。

1
2
3
4
typedef struct DNode{	//定义双链表结点类型
    ElemType data;	//数据域
    struct NDod *prior,*next;	//前驱和后继指针
}DNode,*DLinklist;

基本操作

1.插入操作

在双链表中p所指的结点之后插入结点*s

image-20260812112934239

1
2
3
4
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;	//第①步必须在第④步之前

2.删除操作

71073498218af9b2b6d4428061b6e21b

1
2
3
p->next = p->next->next;
q->next->prior = p;
free(q)

循环链表（单）

和单链表的区别：循环单链表的表中最后一个结点的指针不是NULL，而改为指向头节点，从而整个链表形成一个环。

循环单链表的判空条件：不是头节点的指针是否为空，而是头节点的指针是否等于头指针L。

优点：循环单链表可以从表中的任意一个结点开始遍历整个链表，而不是只能从表头开始遍历。（只是效率是On）

有时，对循环单链表可以不设头指针仅设尾指针，对表头表尾插入元素都只要O(1)。

静态链表

静态链表是用数组描述的链式存储结构。

与普通链表中的指针不同的是，这里的指针是结点在数组中的相对地址（数组下标），也称游标。

Tips：

在尾部添加元素→用尾指针

双向遍历/插入/删除→双链表

循环问题→循环链表

顺序表和链表的比较

存取读写：链表只能从表头开始依次顺序存取。

查找：

  • 对于按值查找：顺序表无序时：两者均为On；顺序表有序时，可采用折半查找，Olog₂n。
  • 对于按序号查找：顺序表O1，链表On。

插入和删除：顺序表需要移动半个表长的元素。链表只需修改相关结点的指针域（good！）

大题部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 1.算法思想:先设置两个指针p和q，初始时都指向链表的第一个有效节点（即头节点list的下一个结点）
// ①让指针p先沿链表移动k步。
// ②如果链表长度不足k，说明查找失败，直接返回0.
// ③如果p成功移动了k步，则让指针q和p同时同步向后移动。
// ④当指针p移动到链表末尾（指向NULL）时，指针q恰好指向的是链表的倒数第k个结点。

// 2.实现过程

// 链表结点数据结构定义
typedef struct LNode{
    int data;
    struct LNode *link;	//此处用link，平时自己用next的
}LNode,*LinkList;

//算法函数
int Search_k(LinkList,int k){
    LNode *p = list->link;	//指针p指向第一个数据节点
    LNode *q = list->link;	//指针q指向第一个数据节点
    int count = 0;
    
    //步骤一，让指针p先走k步
    while(p!=NULL && count<k){
        p = p->link;
        count++;
    }
    
    //步骤二，如果链表长度不足k，查找失败，返回0
    if(count<k){
        return 0;
    }
    
    //步骤三，p和q同时向后移动，直到p走到链表末尾。
    while(p!=NULL){
        p = p->link;
        q = q->link;
    }
    
    //步骤四，此时q正好是倒数第k个结点，输出数据并返回1
    return("%d",q->data);
    return 1;
}

// 3.
// 时间复杂度O(n)【只需对链表进行一趟扫描】
// 空间复杂度O(1)

d1208cab62ed1be4cf8a96101df9dd24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 1.算法思想：两个链表在合并前的长度可以不同，如果直接用两个指针从各自的头部同时出发，它们无法同时到达公共结点。我们要做的，就是消除这个长度差。
// ①求出长度：首先分别遍历两个链表，计算出它们的长度len1和len2。
// ②对齐起点：计算长度差值d=|len1-len2|。让较长的链表的指针先向前移动d步。此时，两个指针距离链表末尾的剩余长度是相同的。
// ③同步行进查找：让两个指针同步向后移动。在移动的过程中，比较两个指针指向的结点地址是否相同。第一个地址相同的结点，即为共同后缀的起始位置。

// 2.实现过程：

// 单链表定义
typedef struct Node{
    char data;
    struct Node *next;
}Node;

// 辅助函数：求头节点的单链表实际数据长度（不算头节点）
int getLength(Node *head){
    int len = 0;
    Node *p = head->next;	//从第一个实际数据节点开始计数，头节点不算。
    while(p!=NULL){
        len++;
        p = p->next;
    }
    return len;
}

// 算法：查找共同后缀起始起点
Node* findCommonSuffix(Node *str1,Node *str2){
    int len1 = getLength(str1);
    int len2 = getLength(str2);
    
    Node *p = str1->next;	//p指向链表1的第一个实际数据节点
    Node *q = str2->next;	//q指向链表2的第一个实际数据节点
    
    // 判断哪个链表更长，并让长链表的指针先走d步
    if(len1>len2){
        int d = len1-len2;
        while(d>0){
            p = p->next;
            d--;
        }
    }else{
        int d = len2-len1;
        while(d>0){
            q = q->next;
            d--;
        }
    }
    
    //同步向后移动，比较结点地址(注意：是比较指针指向的内存地址p==q)
    while(p!=NULL && q!=NULL){
        if(p==q){
            return p;
        }
        p = p->next;
        q = q->next;
    }
    
    return NULL;	//如果没有共同后缀，返回NULL。
}

//3.
//时间复杂度：O(n+m)
//空间复杂度：O(1

47bad6bd882d17bd1a43567e830df2e3

1

d2e3ebd3d13cf194ae42447e24da76ee

1