【题目1】试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间的复杂度为O(1)
【分析】就地逆置意味着不可以再额外申请空间进行处理，而必须从链表本身做文章。可以将头结点分离出来，然后按照头插法，进行逆置操作；也可以灵活运用多个指针遍历反转next，进行更加符合“就地“原则的逆置操作。
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
|
void reverse_1(LinkList L) {
LNode *p, *r;
p = L->next;
L->next = NULL;
while(p) {
r = p->next;
p->next = L->next;
L->next = p;
p = r;
}
}
void reverse_2(LinkList L) {
LNode *r, *p, *t;
p = L->next;
t = p->next;
p->next = NULL;
while (t) {
r = p;
p = t;
t = t->next;
p->next = r;
}
L->next = p;
}
|
【题目2】给定两个单链表，试分析找出两个链表的公共结点的思想。
【分析】这一题需要理解“公共结点“的含义，不同于数组存储的顺序表中某两个位置的值相等，链表中的公共元素意味着数据域和指针域都相等，也就意味着指向内存中同一个结点，而这一结点之后的所有结点都是一样的（每个结点有且仅有一个后继）。
明白了这个概念后，我们来思考一下，如果两个链表的长度相同，那么同时向后遍历，每次遍历都比较，如果结点相同则返回。但是如果两个链表长度不同又该如何处理呢？那么就先遍历两个链表，计算两者的长度，长的链表先进行遍历，遍历步数为两者长度之差，这时两者剩余的结点长度相同，同时遍历即可。
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
| LNode *findCommonNode(LinkListt A, LinkList B){
int len_a = 0, len_b = 0;
LNode *pa = A;
LNode *pb = B;
while(pa){
pa = pa->next;
len_a++;
}
while(pb){
pb = pb->next;
len_b++;
}
pa = A;
pb = B;
if (len_a > len_b){
int diff = len_a - len_b;
while(diff--) {
pa = pa->next;
}
}
if (len_b > len_a) {
int diff = len_b - len_a;
while(diff--) {
pb = pb->next;
}
}
while(pa && pb) {
pa = pa->next;
pb = pb->next;
if (pa == pb) {
return pa;
}
}
return NULL;
}
|
【题目3】设有一个带头结点的非循环双链表，其每个结点中除有pre、data和next域外，还有一个访问频度域freq，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令值为x的结点中freq域的值增1，并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate（L, x)函数，返回找到结点的地址，类型为指针型。
【分析】本题中的Locate函数不同于一般的根据值寻找位置的函数，不仅需要返回元素的位置，而且在这之前需要对链表中结点的freq域作相应的修改，使得频繁访问的结点总是靠近表头，在每次调用函数Locate寻找到结点时，需要先将结点前移，然后返回其地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| DNode *Locate(DLinkList &L, ElemType x) {
DNode *p = L->next;
while (p && p->data != x) p = p->next;
if (!p) return NULL;
else {
p->freq++;
p->pre->next = p->next;
p->next->pre = p->pre;
DNode *q = p->pre;
while (q != L && q->freq <= p->freq) q = q->pre;
q->next->pre = p;
p->pre = q;
p->next = q->next;
q->next = p;
return p;
}
}
|
【题目4】单链表有环，是指单链表的最后一个结点的指针指向了单链表中的某个结点（通常单链表中的最后一个指针域是空的）。试编写算法判断单链表是否存在环。如果有环，返回环的入口结点。
【分析】此题需要用到一些数学推理，先设置两个快慢指针fast,slow,slow每次走一步，fast每次走两步。假设链表有环，那么当slow走到环的入口时，fast已经走到了环内，之后slow与fast均在环内移动。当fast与slow第一次相遇时，slow尚未走完一整个环的距离，记此时slow在环上走的距离为x，链表起点到环的入口的距离为a，则slow走的距离为a+x,而fast走的距离为2(a+x)，根据fast与slow的位置关系，fast走的距离也可以表示为a+x+nr,其中r是环的周长，n是fast走过的圈数。将fast的距离的两种表示方式写成等式，可以得到a = n * r - x,或a = (n - 1) * r + (r - x),也即链表起点到环入口的距离等于若干个环的周长加上周长减slow到入口的距离，此时设置两个指针p1,p2，p1指向链表起点，p2指向slow的位置，同时移动， 当p1到达环入口时，p2走完若干圈并多走了r-x的距离，恰好也处于环的入口，此时即找到环的入口位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| LNode *FindLoopStart(LNode *head) {
LNode *fast = head, *slow = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return NULL;
LNode *p1 = head, *p2 = slow;
while(p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
|
【题目5】设有一个长度为n（n为偶数）的不带头结点的单链表，且结点值都大于0，设计算法求这个单链表的最大孪生和。孪生和的定义为一个结点值与其孪生结点值之和，对于第i个结点（从0开始），其孪生结点为第n-i-1个结点。
【分析】由于这题给的是链表，无法进行随机访问，所以最简单的暴力解法就是对于每个结点，遍历链表寻找其孪生结点进行求和运算，找出最大值，时间复杂度为O(n2)。可以考虑空间换时间的方法，将链表中的元素存储到数组中，然后利用数组的随机访问的特性进行计算最大值，时间复杂度为O(n),空间复杂度为O(n)。本题亦可以将链表的后半部分进行逆置，然后依次遍历求和，时间复杂度为O(n),空间复杂度为O(1)。
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
|
int PairSum(LinkList L) {
LNode *fast = L, *slow = L;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
LNode *p = slow, *s, *temp = p->next;
p -> next = NULL;
while(temp != NULL) {
s = p;
p = temp;
temp = temp->next;
p->next = s;
}
LNode *q = L;
int maxSum = 0;
while(p!=NULL) {
int curSum = p->data + q->data;
if (curSum > maxSum) maxSum = curSum;
p = p->next;
q = q->next;
}
return maxSum;
}
int PairSum_2(LinkList L) {
LNode *p = L;
int len = 0;
while (p != NULL) {
p = p->next;
len++;
}
int *arr = (int *) malloc(len * sizeof(int));
p = L;
int idx = 0;
while (p != NULL) {
arr[idx++] = p->data;
p = p->next;
}
int i = 0, j = len - 1;
int maxSum = 0;
while (i < j) {
int curSum = arr[i] + arr[j];
if (curSum > maxSum) maxSum = curSum;
i++;
j--;
}
return maxSum;
}
|
【题目6 2015统考真题】用单链表保存m个整数，结点的结构为{data,link},且|data| <= n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其他绝对值相等的结点。例如，若给定的单链表的head如下：
head -> 21 -> -15 -> -15 -> -7 -> 15
则删除结点后的head为
head -> 21 -> -15 -> -7
【分析】题目中要求时间复杂度尽可能高效，暗示了利用空间换时间的思路来解决问题。单链表中的data存在范围的限制，任意|data|均不超过n，所以可以生成一个长度为n+1的数组，记录链表中绝对值已存在的data，遇到绝对值重复的data则进行删除。时间复杂度为O(n),空间复杂度为O(n)。
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
| typedef struct LNode {
int data;
struct LNode *link;
} LNode;
void DeleteSameAbs(LNode *head, int n) {
int *arr = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i < n + 1; i++) {
arr[i] = 0;
}
LNode *p = head, *r;
while(p != NULL) {
int val = p->link->data;
if (val < 0) val = -val;
if (arr[val] == 0) {
arr[val] = 1;
p = p->link;
}
else {
r = p->link;
p->link = r->link;
free(r);
}
}
free(arr);
}
|
【题目7 2019统考真题】设线性表L=(a1,a2,a3,...an-2,an-1,an)采用带头结点的单链表存储，链表中的结点定义如下：
1
2
3
4
| typedef struct node {
int data;
struct node *next;
}NODE;
|
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a1,an,a2,an-1,a3,an-2,...)
【分析】观察重新排列后的L'，可知，算法将L拆分成了两个部分，将后半部分进行了逆置，然后与前半部分交叉合并。故本题分为三个步骤，先找寻到链表的中间结点，然后将链表的后半部分进行逆置操作，最后将逆置的后半部分交替插入前半部分即可。
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
| void ChangeList(NODE *h) {
NODE *slow = h, *fast = h;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
NODE *r, *s = slow->next, *t = s->next;
slow->next = NULL;
s->next = NULL;
while(t != NULL) {
r = s;
s = t;
t = t->next;
s->next = r;
}
NODE *p = h->next;
NODE *q
while (s != NULL) {
q = s->next;
s->next = p->next;
p->next = s;
p = s->next;
s = q;
}
}
|
链表中一些重要的操作，比如逆置，归并两个链表，双指针（定位链表中间结点）需要非常熟悉地掌握，不必拘泥于书上的代码实现，要在真正理解的基础上形成自己的代码书写风格。
