数据结构02：线性表 链表习题02[C++]

考研笔记整理~🥝🥝

之前的博文链接在此：数据结构02：线性表[顺序表+链表]_线性链表-CSDN博客~🥝🥝

本篇作为链表的代码补充，供小伙伴们参考~🥝🥝

• 第1版：王道书的课后习题~🧩🧩

编辑：梅头脑🌸

参考用书：王道考研《2025年 数据结构考研复习指导》

---

目录

🧵09年 查找单链表倒数第k个位置的节点

🧵12年 寻找单链表的相同后缀

🧵15年 删除单链表中绝对值相等的节点

🧵19年 重新排列单链表中的各节点

🔚结语

---

🧵09年 查找单链表倒数第k个位置的节点

🧩题目

📇解题思路1（1个指针，遍历2轮）

• 算法思路：
  • 创建1个指针；
  •  第1遍从头到尾遍历链表，记录链表的长度length，计算出倒数第k个节点的位置；
  •  第2遍从头到尾遍历链表，​寻找length-k的位置。
• 时间复杂度：O(n)，其中 n 为链表的长度，只遍历了2轮。
• 空间复杂度：O(1)。只使用了常数个辅助指针。

⌨️解题代码1

#include <iostream>
#include <vector>
using namespace std;

typedef struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
    ListNode() : data(0), next(nullptr) {}
}LNode, * LinkList;

LinkList CreateList(vector<int>& vec) {
    LinkList head = new ListNode();
    LinkList p = head;
    for (int i = 0; i < vec.size(); i++) {
        LinkList temp = new ListNode(vec[i]);
        p->next = temp;
        p = p->next;
    }
    return head;
}

int findKthFromEnd(ListNode* head, int k) {
    if (head == nullptr || k <= 0) {
        return 0; // 链表为空或 k 不合法，返回 0
    }

    ListNode* p = head;
    int length = 0;

    while (p->next != nullptr) {
        p = p->next;
        length++;
    }

    if (length < k) { return 0; }

    p = head->next;
    while (length > k) {
        p = p->next;
        length--;
    }

    cout << "倒数第 " << k << " 个位置上的结点的值为：" << p->data << endl;
    return 1; // 返回 1 表示查找成功
}

int main() {
    vector <int> vec = { 1, 2, 3, 4, 5 };
    LinkList head = CreateList(vec);
    int k = 2; // 要查找的倒数第 k 个位置

    int found = findKthFromEnd(head, k);
    if (found == 0) {
        cout << "未找到倒数第 " << k << " 个位置上的结点" << endl;
    }

    return 0;
}

📇解题思路2（2个指针，遍历1轮）

• 算法思路：
  • 创建2个指针，快指针先前进k个节点，慢指针从链表头开始遍历；
  •  遍历1轮，快慢指针一起向后移动，当快指针指向表尾时，慢指针指向的节点即为所求。
• 时间复杂度：O(n)，其中 n 为链表的长度，只遍历了1轮。
• 空间复杂度：O(1)。只使用了常数个辅助指针。

⌨️解题代码2

#include <iostream>
#include <vector>
using namespace std;

typedef struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
    ListNode() : data(0), next(nullptr) {}
}LNode, * LinkList;

LinkList CreateList(vector<int>& vec) {
    LinkList head = new ListNode();
    LinkList p = head;
    for (int i = 0; i < vec.size(); i++) {
        LinkList temp = new ListNode(vec[i]);
        p->next = temp;
        p = p->next;
    }
    return head;
}

int findKthFromEnd(ListNode* head, int k) {
    if (head == nullptr || k <= 0) {
        return 0; // 链表为空或 k 不合法，返回 0
    }

    ListNode* slow = head, * fast = head;

    // 快指针先向前移动 k 步
    for (int i = 0; i < k; ++i) {
        if (fast == nullptr) {
            return 0; // 如果链表长度小于 k，返回 0
        }
        fast = fast->next;
    }

    // 快慢指针一起向前移动，直到快指针到达链表尾部
    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    cout << "倒数第 " << k << " 个位置上的结点的值为：" << slow->data << endl;
    return 1; // 返回 1 表示查找成功
}

int main() {
    vector <int> vec = { 1, 2, 3, 4, 5 };
    LinkList head = CreateList(vec);
    int k = 2; // 要查找的倒数第 k 个位置

    int found = findKthFromEnd(head, k);
    if (found == 0) {
        cout << "未找到倒数第 " << k << " 个位置上的结点" << endl;
    }

    return 0;
}

---

🧵12年 寻找单链表的相同后缀

🧩题目

📇解题思路

• 算法思路：
  • 创建2个指针；
  • 2个指针从头到尾遍历链表，分别计算str1的长度length1与str2的长度length2；
  • 较长的链表先前进|length1-length2|个节点，较短的链表从链表头开始遍历；
  •  遍历1轮，两个链表的指针一起向后移动，当指针指向的节点地址相同时（注意哦，地址相同一定数据相同，而数据相同不一定地址相同），节点位置即为所求。
• 时间复杂度：O(n)，其中 n 为链表的长度，2个链表各遍历了2次。
• 空间复杂度：O(1)。只使用了常数个辅助指针。

⌨️解题代码

#include <iostream>
#include <vector>
using namespace std;

typedef struct ListNode {
    char data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
    ListNode() : data(0), next(nullptr) {}
}LNode, * LinkList;

LinkList CreateList(vector<char>& vec) {
    LinkList head = new ListNode();
    LinkList p = head;
    for (int i = 0; i < vec.size(); i++) {
        LinkList temp = new ListNode(vec[i]);
        p->next = temp;
        p = p->next;
    }
    return head;
}

LinkList CreateCommonList(LinkList head1, LinkList head2) {
    if (head1 == nullptr || head1->next == nullptr) return nullptr;
    if (head2 == nullptr || head2->next == nullptr) return nullptr;

    LNode* p1 = head1->next;
    LNode* p2 = head2->next;
    int length1 = 0, length2 = 0;

    // 统计两个链表的长度
    while (p1 != nullptr && p2 != nullptr) {
        p1 = p1->next; length1++;
        p2 = p2->next; length2++;
    }
    while (p1 != nullptr) { p1 = p1->next; length1++; }
    while (p2 != nullptr) { p2 = p2->next; length2++; }

    p1 = head1->next;
    p2 = head2->next;

    // 较长的链表指针后移，使两个链表距离末尾的长度相等
    int len1 = length1, len2 = length2;
    while (labs(len1 - len2) > 0) {
        if (len1 > len2) {
            p1 = p1->next;
            len1--;
        }
        else {
            p2 = p2->next;
            len2--;
        }
    }

    // 寻找链表所有的公共节点下标，并存储在common中
    int i = 0;
    int j = 0;
    vector<int> common;
    while (p1 != nullptr && p2 != nullptr) {
        i++;
        if (p1->data == p2->data) {
            common.push_back(i); j++;
            cout << "找到了第 " << j << " 个公共节点：" << p1->data << endl;
        }
        if (p1 != nullptr) p1 = p1->next;
        if (p2 != nullptr) p2 = p2->next;
    }
    if (common.empty() == true) {
        cout << "错误：两个链表没有公共节点" << endl;
        return nullptr;
    }

    // 寻找Common中小于末尾节点且没有出现的最大整数
    int com = common[0];
    for (int k = common.size() - 1; k > 0; k--) {
        if (common[k] != common[k - 1] + 1) {
            com = common[k];
            break;
        }
    }
    cout << "最后一个公共节点与较短链表头部节点的距离是：" << com << endl;

    // 较长的链表指针后移，使两个链表距离末尾的长度相等
    LNode* q1 = head1;
    LNode* q2 = head2;
    len1 = length1;
    len2 = length2;
    while (labs(len2 - len1) > 0) {
        if (len1 > len2) {
            q1 = q1->next;
            len1--;
        }
        else {
            q2 = q2->next;
            len2--;
        }
    }
    while (com > 1 && q1->next != nullptr && q2->next != nullptr) {
        q1 = q1->next;
        q2 = q2->next;
        com--;
    }
    if (q1 != nullptr && q2 != nullptr) {
        cout << "最后一个公共节点是：" << q1->next->data << endl;
        q1->next = q2->next; // 合并q2链表与q1链表
        return head1;
    }
    else {
        cout << "错误：两个链表没有公共节点" << endl;
        return nullptr;
    }
}

LNode* FindCommon(LinkList str1, LinkList str2) {
    if (str1 == nullptr || str1->next == nullptr) return nullptr;
    if (str2 == nullptr || str2->next == nullptr) return nullptr;

    LNode* p1 = str1->next;
    LNode* p2 = str2->next;
    int length1 = 0, length2 = 0;

    // 统计两个链表的长度
    while (p1 != nullptr && p2 != nullptr) {
        p1 = p1->next; length1++;
        p2 = p2->next; length2++;
    }
    while (p1 != nullptr) { p1 = p1->next; length1++; }
    while (p2 != nullptr) { p2 = p2->next; length2++; }

    p1 = str1->next;
    p2 = str2->next;

    // 较长的链表指针后移，使两个链表距离末尾的长度相等
    int len1 = length1, len2 = length2;
    while (labs(len1 - len2) > 0) {
        if (len1 > len2) {
            p1 = p1->next;
            len1--;
        }
        else {
            p2 = p2->next;
            len2--;
        }
    }

    // 寻找链表共同后缀的起始节点
    int i = 0;
    while (p1 != nullptr && p2 != nullptr) {
        i++;
        if (p1 == p2) {
            cout << "找到了第 1 个公共节点：" << p1->data << endl;
            return p1;
        }
        if (p1 != nullptr) p1 = p1->next;
        if (p2 != nullptr) p2 = p2->next;
    }

    cout << "错误：两个链表没有公共节点" << endl;
    return nullptr;
}

int main() {
    vector <char> vec1 = { 'b', 'e', 'i', 'n', 'g' };
    vector <char> vec2 = { 'l', 'o', 'a', 'd', 'i', 'n', 'g' };
    //vector <char> vec1 = {'b', 'e', 'i', 'b', 'e'};
    //vector <char> vec2 = { 'l', 'o', 'b', 'e', 'c', 'b', 'e'};
    //vector <char> vec1 = { 'b', 'e', 'b', 'b', 'e' };
    //vector <char> vec2 = { 'b', 'e' };
    //vector <char> vec1 = { 'b', 'e' };
    //vector <char> vec2 = { 'e' };
    //vector <char> vec1 = { 'e' };
    //vector <char> vec2 = { 'e' };
    //vector <char> vec1 = { 'e', 'b' };
    //vector <char> vec2 = { 'e' };
    LinkList head1 = CreateList(vec1);
    LinkList head2 = CreateList(vec2);
    LinkList head = CreateCommonList(head1, head2);

    LNode* p1 = head1;
    LNode* p2 = head2;
    cout << "链表1：" << endl;
    while (p1->next != nullptr) {
        cout << "节点数据：" << p1->next->data << " ";
        cout << "节点地址:" << p1->next << endl;
        p1 = p1->next;
    }

    cout << "链表2：" << endl;
    while (p2->next != nullptr) {
        cout << "节点数据:" << p2->next->data << " ";
        cout << "节点地址:" << p2->next << endl;
        p2 = p2->next;
    }

    cout << endl;
    cout << "——以上均为创建题目要求的环境，以下是解题过程——" << endl;

    LNode* result = FindCommon(head1, head2);

    return 0;
}

备注：考试的时候写FindCommon那段函数的内容就可以了，其它的内容都是为了建立题目中的环境，方便测试一下代码运行的实际效果~

（不是，我到现在都没想明白，哪个大机灵鬼会使用这种方法存单词啊🥲...  ）

---

🧵15年 删除单链表中绝对值相等的节点

🧩题目

📇算法思路

• ​算法思想：
  • 创建哈希表；
  • 指针从前向后逐个遍历链表节点：
    • 如果，该节点的绝对值不存在于哈希表，将该节点记入哈希表，指针向后移动；
    • 否则，该节点的绝对值已经存入哈希表内，则执行删除操作，指针向后移动； 
• 时间复杂度：O(n)，其中 n 为链表的长度。遍历链表一次，删除重复的绝对值结点。
• 空间复杂度：O(n)，其中 n 为链表的长度。使用了一个哈希表来记录每个绝对值出现的次数。

⌨️算法代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

typedef struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
    ListNode() : data(0), next(nullptr) {}
}LNode, * LinkList;

LinkList CreateList(vector<int>& vec) {
    LinkList head = new ListNode();
    LinkList p = head;
    for (int i = 0; i < vec.size(); i++) {
        LinkList temp = new ListNode(vec[i]);
        p->next = temp;
        p = p->next;
    }
    return head;
}

LinkList Delete_the_Same_Abs_Node(ListNode* head) {
    if (head == nullptr) { return 0; }

    ListNode* p = head->next;
    unordered_map<int, int> nums;   // 记录每个绝对值出现的次数

    // 遍历链表，删除重复的绝对值结点
    while (p != nullptr) {
        if (nums[abs(p->data)] == 0) {
            nums[abs(p->data)]++;
        }
        else {
            ListNode* q = head;
            while (q->next != p) {
                q = q->next;
            }
            q->next = p->next;
            delete p;
            p = q;
        }
        p = p->next;
    }

    return head;
}

int main() {
    vector <int> vec = { 21, -15, -15, -7, 15 };
    LinkList head = CreateList(vec);

    LinkList newhead = Delete_the_Same_Abs_Node(head);
    if (newhead == nullptr) {
        cout << "链表为空" << endl;
    }
    else {
        LNode* p = newhead->next;
        while (p != nullptr) {
            cout << p->data << " ";
            p = p->next;
        }
    }

    return 0;
}

---

🧵19年 重新排列单链表中的各节点

🧩题目

📇解题思路

• ​算法思想：
  • 使用快慢指针，每次快指针进1步，慢指针进2步。快指针到终点时，慢指针指向中点。将链表的位置从中间断开，这样我们就可以得到两个链表；
    • L = (a_1, a_2, ... a_n/2)
    • slow->next = (a_n/2+1, a_n/2+2, ... a_n);
  • 逆置slow->next后面的链表，并记为L2：
    • L = (a_1, a_2, ... a_n/2)
    • L2 = (a_n, a_n-1, ... a_n/2+1);
  • 合并2个链表：L2使用头插法，逐一插入L1每个节点之间，实现逆置效果；
    • L'=(a_1,a_n,a_2,a_n-1,a_3,a_n-2,…)
• 时间复杂度：O(n)，其中 n 为链表的长度。遍历链表 2 次，删除重复的绝对值结点。
• 空间复杂度：O(1)，只需要常数个辅助变量。

⌨️算法代码

#include <iostream>
#include <vector>
using namespace std;

typedef struct node {
	int data;
	struct node* next;
}NODE;

NODE* CreateNode(int data) {
	NODE* node = new NODE();
	node->data = data;
	node->next = nullptr;
	return node;
}

NODE* CreateList(const vector<int>& vec) {
	NODE* head = new NODE();
	NODE* p = head;
	for (int i = 0; i < vec.size(); i++) {
		NODE* temp = CreateNode(vec[i]);
		p->next = temp->next;
		p->next = temp;
		p = p->next;
	}
	return head;
}

bool Resort(NODE* L) {
	if (L == nullptr || L->next == nullptr) return false;

	NODE* p = L->next;
	NODE* slow = new NODE(); NODE* fast = new NODE();
	slow->next = L; fast->next = L;

	// 快慢指针找到链表的中间节点
	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next;
		if (fast->next != nullptr) fast = fast->next;
	}

	// 将链表的后半部分逆序
	NODE* L2 = new NODE(); NODE* pre = L2->next;
	NODE* cur = slow->next;	slow->next = nullptr;
	NODE* next = nullptr;
	while (cur != nullptr) {
		next = cur->next;		// next用于记录下一轮循环起始点
		cur->next = nullptr;	// 从链表中摘下cur

		cur->next = L2->next;	// 将cur插入到L2中（头插法）
		L2->next = cur;

		cur = next;				// cur指向下一轮循环的起始点next
	}

	// 将链表的前半部分和逆序后的后半部分合并
	NODE* p1 = L->next;
	NODE* p2 = L2->next;
	while (p1 != nullptr && p2 != nullptr) {
		L2->next = p2->next;	// 从L2中取出一个节点
		p2->next = nullptr;

		p2->next = p1->next;	// 将L2的节点插入到L中
		p1->next = p2;

		p1 = p1->next;			// 将p1指向L1的下一个节点
		if (p1 != nullptr) p1 = p1->next;
		p2 = L2->next;			// 将p2指向L2的下一个节点
	}

	return true;
}

int main()
{
	vector<int> vec = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
	// vector<int> vec = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
	NODE* L = CreateList(vec);

	bool result = Resort(L);

	cout << "result: " << result << endl;
	cout << "L: ";
	while (L->next != nullptr) {
		cout << L->next->data << " ";
		L = L->next;
	}
	cout << endl;

	L = nullptr;

	return 0;
}

📇备注

因为审错了题，我还写出过这样一个代码...L'=(a_1,a_n,a_3,a_n-2,a_5,a_n-4,…)...

虽然没什么用，但是鉴于我这么菜，想了很久的逻辑，所以也厚脸皮地贴在这里留着自己看了...

（毕竟愿意看我代码的，目前看来，除了好友、网站审核，就是官方培养的僵尸粉了😭...）

#include <iostream>
#include <vector>
using namespace std;

typedef struct node {
	int data;
	struct node* next;
}NODE;

NODE* CreateNode(int data) {
	NODE* node = new NODE();
	node->data = data;
	node->next = nullptr;
	return node;
}

NODE* CreateList(const vector<int>& vec) {
	NODE* head = new NODE();
	NODE* p = head;
	for (int i = 0; i < vec.size(); i++) {
		NODE* temp = CreateNode(vec[i]);
		p->next = temp->next;
		p->next = temp;
		p = p->next;
	}
	return head;
}

bool Resort(NODE* L) {
	if (L == nullptr || L->next == nullptr) return false;

	NODE* p = L->next;
	NODE* L1 = new NODE(); NODE* p1 = L1;
	NODE* L2 = new NODE(); NODE* p2 = L2;

	int count = 1;

	// 将L中的节点分别插入到L1和L2中
	while (p != nullptr) {
		p = L->next;			// 摘下L的下一个节点p
		if (p == nullptr) break;	// 如果p为空，则退出循环
		L->next = p->next;
		p->next = nullptr;

		if (count % 2 == 1) {	// 将p使用尾插法插入到L1中
			p1->next = p;
			p1 = p1->next;
		}
		else {					// 将p使用头插法插入到L2中
			p->next = p2->next;
			p2->next = p;
		}
		count++;
	}

	L->next = nullptr;
	p1 = L1->next; p2 = L2->next; p = L;
	while (p1 != nullptr || p2 != nullptr) {
		if (p1 != nullptr) {
			L1->next = p1->next;	// 从L1中取出一个节点
			p1->next = p->next;			// 将L1的节点插入到L中
			p->next = p1;
			p = p->next;
			p1 = L1->next;			// 将p1指向L1的下一个节点
		}

		if (p2 != nullptr) {
			L2->next = p2->next;	// 从L2中取出一个节点
			p2->next = p->next;			// 将L2的节点插入到L中
			p->next = p2;
			p = p->next;
			p2 = L2->next;			// 将p2指向L2的下一个节点
		}
	}

	return true;
}

int main()
{
	vector<int> vec = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
	// vector<int> vec = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
	NODE* L = CreateList(vec);

	bool result = Resort(L);

	cout << "result: " << result << endl;
	cout << "L: ";
	while (L->next != nullptr) {
		cout << L->next->data << " ";
		L = L->next;
	}
	cout << endl;

	L = nullptr;

	return 0;
}

---

🔚结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~😶‍🌫️

我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，收到点赞的话，博主肝文的动力++~🌟🌟

同系列的博文：🌸数据结构_梅头脑_的博客-CSDN博客

同博主的博文：🌸随笔03 笔记整理-CSDN博客