二、链表（12 题）
二、链表（12 题）¶
默认结构¶
除非特别说明，本节单链表均带头结点。
1. 带头结点单链表的原地逆置¶
void reverseList(LinkList L) {
LinkList p = L->next;
L->next = NULL;
while (p != NULL) {
LinkList next = p->next;
p->next = L->next;
L->next = p;
p = next;
}
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 依次摘下原链表结点并头插到新链表中；必须先保存 p->next，否则会丢失未处理部分。
2. 处理无序正整数链表中的唯一最小值结点¶
要求：找到唯一最小值结点；若其值为奇数，则与后继结点交换结点位置；若为偶数，则删除其后继结点。若最小值结点没有后继，返回 false。
bool handleMinNode(LinkList L) {
if (L == NULL || L->next == NULL)
return false;
LinkList minPrev = L;
for (LinkList p = L; p->next != NULL; p = p->next) {
if (p->next->data < minPrev->next->data)
minPrev = p;
}
LinkList minNode = minPrev->next;
LinkList successor = minNode->next;
if (successor == NULL)
return false;
if (minNode->data % 2 == 0) {
minNode->next = successor->next;
free(successor);
} else {
minNode->next = successor->next;
successor->next = minNode;
minPrev->next = successor;
}
return true;
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 遍历时记录最小值结点的前驱，便于后续删除或交换结点；交换的是链接关系，不是数据域。
3. 删除递增链表中的重复结点，仅保留第一个¶
void uniqueOrderedList(LinkList L) {
LinkList p = L->next;
while (p != NULL && p->next != NULL) {
if (p->data == p->next->data) {
LinkList duplicate = p->next;
p->next = duplicate->next;
free(duplicate);
} else {
p = p->next;
}
}
}
复杂度： 时间 O(n)，额外空间 O(1)。
4. 按绝对值去重（2015 年统考题）¶
单链表保存 m 个整数，且 |data| <= n。对于绝对值相等的结点，仅保留第一次出现的结点。
bool uniqueByAbsoluteValue(LinkList L, int n) {
bool *seen = (bool *)calloc(n + 1, sizeof(bool));
if (seen == NULL)
return false;
LinkList p = L;
while (p->next != NULL) {
int value = p->next->data;
int key = value >= 0 ? value : -value;
if (!seen[key]) {
seen[key] = true;
p = p->next;
} else {
LinkList duplicate = p->next;
p->next = duplicate->next;
free(duplicate);
}
}
free(seen);
return true;
}
复杂度： 时间 O(m+n)（其中初始化辅助数组为 O(n)），额外空间 O(n)。
5. 按正负拆分链表并保持原相对次序¶
将链表 A 拆分为 A、B：A 保留非负结点，B 保存负数结点。
LinkList splitBySign(LinkList A) {
LinkList B = (LinkList)malloc(sizeof(LNode));
if (B == NULL)
return NULL;
B->next = NULL;
LinkList p = A;
LinkList tailB = B;
while (p->next != NULL) {
if (p->next->data >= 0) {
p = p->next;
} else {
LinkList node = p->next;
p->next = node->next;
tailB->next = node;
tailB = node;
}
}
tailB->next = NULL;
return B;
}
复杂度： 时间 O(n)；除 B 的头结点外，额外空间 O(1)。
6. 将 {a1,b1,a2,b2,...,an,bn} 拆为 {a1,...,an} 和 {bn,...,b1}¶
LinkList splitAlternating(LinkList A) {
LinkList B = (LinkList)malloc(sizeof(LNode));
if (B == NULL)
return NULL;
B->next = NULL;
LinkList p = A;
int position = 1;
while (p->next != NULL) {
if (position % 2 == 1) {
p = p->next;
} else {
LinkList node = p->next;
p->next = node->next;
node->next = B->next;
B->next = node;
}
position++;
}
return B;
}
复杂度： 时间 O(n)；除 B 的头结点外，额外空间 O(1)。
核心思路： 奇数位置结点留在 A；偶数位置结点从 A 摘下并头插到 B，因此 B 中次序自动反转。
7. 将两个递增链表原地合并为非递减链表¶
void mergeOrderedLists(LinkList A, LinkList B) {
LinkList p = A->next;
LinkList q = B->next;
LinkList tail = A;
while (p != NULL && q != NULL) {
if (p->data <= q->data) {
tail->next = p;
p = p->next;
} else {
tail->next = q;
q = q->next;
}
tail = tail->next;
}
tail->next = (p != NULL) ? p : q;
B->next = NULL;
}
复杂度： 时间 O(m+n)，额外空间 O(1)。
核心思路： p、q 分别扫描两个链表，tail 维护结果链表尾部，最后直接拼接尚未遍历完的部分。
8. 求两个递增链表的去重并集，并存回 A¶
要求复用 A、B 的原有结点空间；下面的实现也能去除单个输入链表内部已有的重复值。
void unionOrderedLists(LinkList A, LinkList B) {
LinkList p = A->next;
LinkList q = B->next;
LinkList tail = A;
bool hasLast = false;
int lastValue = 0;
A->next = NULL;
B->next = NULL;
while (p != NULL || q != NULL) {
LinkList node;
if (q == NULL || (p != NULL && p->data <= q->data)) {
node = p;
p = p->next;
if (q != NULL && node->data == q->data) {
LinkList duplicate = q;
q = q->next;
free(duplicate);
}
} else {
node = q;
q = q->next;
}
if (!hasLast || node->data != lastValue) {
tail->next = node;
tail = node;
lastValue = node->data;
hasLast = true;
} else {
free(node);
}
}
tail->next = NULL;
}
复杂度： 时间 O(m+n)，额外空间 O(1)。
校订注：原稿只在
p->data == q->data时去重；若A或B自身含有重复值，仍会把重复结点带入结果。本版补齐了这种情况。
9. 找出两个链式单词的公共后缀起始结点（2012 年统考题）¶
int listLength(LinkList L) {
int length = 0;
for (LinkList p = L->next; p != NULL; p = p->next)
length++;
return length;
}
LinkList firstCommonSuffixNode(LinkList str1, LinkList str2) {
int len1 = listLength(str1);
int len2 = listLength(str2);
LinkList p = str1->next;
LinkList q = str2->next;
while (len1 > len2) {
p = p->next;
len1--;
}
while (len2 > len1) {
q = q->next;
len2--;
}
while (p != NULL && q != NULL) {
if (p == q)
return p;
p = p->next;
q = q->next;
}
return NULL;
}
复杂度： 时间 O(m+n)，额外空间 O(1)。
核心思路： 先计算长度并让较长链表先走长度差，使两个指针距表尾等远；随后同步前进，第一个地址相同的结点就是公共后缀起点。
10. 查找倒数第 k 个结点（2009 年统考题）¶
查找成功时输出结点数据并返回 1，否则返回 0。
int printKthFromEnd(LinkList L, int k) {
if (L == NULL || k <= 0)
return 0;
LinkList fast = L->next;
LinkList slow = L->next;
for (int i = 0; i < k; i++) {
if (fast == NULL)
return 0;
fast = fast->next;
}
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
printf("%d", slow->data);
return 1;
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 先让快指针领先 k 个结点，再让快慢指针同步前进；快指针到达表尾时，慢指针即指向倒数第 k 个结点。
11. 将链表重排为 (a1, an, a2, an-1, ...)（2019 年统考题）¶
LinkList reverseWithoutHead(LinkList head) {
LinkList previous = NULL;
LinkList current = head;
while (current != NULL) {
LinkList next = current->next;
current->next = previous;
previous = current;
current = next;
}
return previous;
}
void reorderList(LinkList L) {
if (L == NULL || L->next == NULL || L->next->next == NULL)
return;
LinkList slow = L->next;
LinkList fast = L->next;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
LinkList second = reverseWithoutHead(slow->next);
slow->next = NULL;
LinkList first = L->next;
while (second != NULL) {
LinkList nextFirst = first->next;
LinkList nextSecond = second->next;
first->next = second;
second->next = nextFirst;
first = nextFirst;
second = nextSecond;
}
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 快慢指针找中点，将后半段逆置，再交替合并前半段与逆置后的后半段。
12. 判断单链表是否有环¶
bool hasCycle(LinkList L) {
LinkList slow = L;
LinkList fast = L;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 若存在环，每次走两步的快指针最终会在环中追上每次走一步的慢指针；若快指针到达 NULL，则无环。