C++单向（循环）链表操作模板
单向链表模板：带头结点。
// 定义单链表结
struct Node
{
int data;
Node *next;
Node(int v = 0): data(v), next(nullptr) {}
};//函数声明部分 Node *createTail(); // 创建链表（尾插入法） Node *createHead(); // 创建链表（头插入法） int getLen(Node *head); // 获取链表长度 Node *getNodeAt(Node *head, int i); // 按序号查找结点 Node *getNodeKey(Node *head, int key); // 按值查找结点 bool insertAt(Node *head, int i, int e);// 指定位置插入结点 bool insertBeforeKey(Node *head, int key, int e); //在指定值结点 “之前” 插入新的结点 bool removeAt(Node *head, int i); // 按序号删除结点 bool removeKey(Node *head, int key); // 按值删除结点 int removeAllKey(Node *head, int key); // 删除所有值为key的结点 void reverseList(Node *head); // 单链表反转 Node *mergeList(Node *h1, Node *h2); // 合并两个有序链表（升序） void bubbleSortList(Node *head); // 单链表排序（冒泡排序） void mergeSortList(Node *head); // 单链表排序（归并排序） void printList(Node *head); // 打印链表 void freeList(Node *head); // 释放链表所占内存
1.创建链表、打印输出链表以及释放链表模板：
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node *next;
Node(int v = 0): data(v), next(nullptr) {}
};
Node *createTail(); // 创建链表（尾插入法）
Node *createHead(); // 创建链表（头插入法）
void printList(Node *head); // 打印链表
void freeList(Node *head); // 释放链表所占内存
int main()
{
// 1.创建链表
//Node *head = createHead();
Node *head = createTail();
printList(head);
freeList(head);
return 0;
}
Node *createTail()
{
// 新结点插入到当前链表的表尾，使其成为当前链表的尾结点。带头结点
// 如果需要：可以把链表的大小或其它信息存储到头结点的data中。
Node *head = new Node();
Node *tail = head;
int data;
//while (scanf("%d", &data) == 1 && data != -1) //（-1结束）
while (scanf("%d", &data), data != -1)
{
tail->next = new Node(data);
tail = tail->next;
}
return head;
}
Node *createHead()
{
// 每次插入的结点都作为链表的第一个结点，带头结点。
// 如果需要：可以把链表的大小或其它信息存储到头结点的data中。
Node *head = new Node();
int data;
//while (scanf("%d", &data) == 1 && data != -1) //（-1结束）
while (scanf("%d", &data), data != -1)
{
Node *p = new Node(data);
p->next = head->next;
head->next = p;
}
return head;
}
// 打印链表所有数据用空格分隔
void printList(Node *head)
{
// 方法一：
Node *cur = head->next;
if (!cur)
return;
printf("%d", cur->data);
cur = cur->next;
while (cur)
{
printf(" %d", cur->data);
cur = cur->next;
}
printf("\n");
/*
// 方法二：
for (Node *cur = head->next; cur; cur = cur->next)
{
if (cur != head->next)
printf(" ");
printf("%d", cur->data);
}
printf("\n");
*/
}
// 释放链表所占内存
void freeList(Node *head)
{
Node *tmp;
while (head)
{
tmp = head;
head = head->next;
delete tmp;
}
}2.获取链表长度：int getLen(Node *head)；。
// 获取链表长度
int getLen(Node *head)
{
int len = 0;
Node *p = head->next;
while (p)
{
len++;
p = p->next;
}
return len;
}3. 按序号查找结点：Node *getNodeAt(Node *head, int i);
Node *getNodeAt(Node *head, int i)
{
// 返回第i个结点指针，i从1开始，没找到返回nullptr。
if (i < 1)
return nullptr;
Node *p = head->next;
int pos = 1;
while (p && pos < i)
{
p = p->next;
pos++;
}
return p;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int i;
scanf("%d", &i);
// 2.返回第i个结点指针
Node *p = getNodeAt(head, i);
if (p)
printf("%d\n", p->data);
else
printf("第%d个结点不存在！\n", i);
// 3.释放链表
freeList(head);
return 0;
}4.按值查找结点：Node *getNodeKey(Node *head, int key);
Node *getNodeKey(Node *head, int key)
{
// 返回第一个值为key的结点指针, 不存在返回nullptr。
Node *p = head->next;
while (p && p->data != key)
{
p = p->next;
}
return p;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int key;
scanf("%d", &key);
// 2.返回第一个值为key的结点指针
Node *p = getNodeKey(head, key);
if (p)
printf("%d\n", p->data);
else
printf("链表中不存在值为%d的结点！\n", key);
// 3.释放链表
freeList(head);
return 0;
}5.指定位置插入结点：bool insertAt(Node *head, int i, int e);
bool insertAt(Node *head, int i, int e)
{
// 在第i个位置前插入值为e的新结点（插入到ai-1与ai之间），使e成为第i个结点。
// i从1开始，i<=1头插，i>长度尾插，返回新头。
if (i < 1)
return false; // 位置非法
Node *p = head;
int pos = 1;
// 找到第 i-1 个结点
while (p->next && pos < i)
{
p = p->next;
pos++;
}
Node *newNode = new Node(e);
newNode->next = p->next;
p->next = newNode;
return true;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int i, x;
scanf("%d%d", &i, &x);
// 2.在n之前插入x
bool flag = insertAt(head, i, x);
if (flag)
printf("插入成功！\n");
else
printf("插入失败！\n");
printList(head);
// 3.释放链表
freeList(head);
return 0;
}6.在指定值结点 “之前” 插入新的结点：bool insertBeforeKey(Node *head, int key, int e);
bool insertBeforeKey(Node *head, int key, int e)
{
Node *p = head;
//while (p->next->data != key && p->next != nullptr)//对空指针取成员 → 程序崩溃！
while (p->next != nullptr && p->next->data != key)// p->next != nullptr 永远放左边
{
p = p->next;
}
if (p->next == nullptr)
return false;
Node *newNode = new Node(e);
newNode->next = p->next;
p->next = newNode;
return true;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int n, x;
scanf("%d%d", &n, &x);
// 2.在n之前插入x
bool flag = insertBeforeKey(head, n, x);
if (flag)
printList(head);
else
printf("%d不存在!\n", n);
// 3.释放链表
freeList(head);
return 0;
}7.按序号删除结点：bool removeAt(Node *head, int i);
bool removeAt(Node *head, int i)
{
if (i < 1)
return false;
//删除第i个结点
Node *p = head;
int pos = 1;
//找到第i-1个结点
while (p->next && pos < i)
{
p = p->next;
pos++;
}
if (!p->next) // i 值非法
return false;
Node *q = p->next;
p->next = q->next;
delete q;
return true;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int i;
scanf("%d", &i);
// 2.删除第i个结点
bool flag = removeAt(head, i);
if (flag)
printf("删除成功\n");
else
printf("删除失败\n");
printList(head);
// 3.释放链表
freeList(head);
return 0;
}8.按值删除结点：bool removeKey(Node *head, int key);
bool removeKey(Node *head, int key)
{
// 删除第一个值为key的结点
Node *p = head;
while (p->next && p->next->data != key)
{
p = p->next;
}
if (!p->next)
return false;
Node *q = p->next;
p->next = q->next;
delete q;
return true;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int key;
scanf("%d", &key);
// 2.删除第一个值为key的结点结点
bool flag = removeKey(head, key);
if (flag)
printf("删除成功\n");
else
printf("删除失败\n");
printList(head);
// 3.释放链表
freeList(head);
return 0;
}9.删除所有值为key的结点：int removeAllKey(Node *head, int key);
int removeAllKey(Node *head, int key)
{
int cnt = 0;
Node *p = head;
while (p->next)
{
if (p->next->data == key)
{
Node *q = p->next;
p->next = q->next;
delete q;
cnt++;
}
else
p = p->next;
}
return cnt;
}
int main()
{
// 1.创建链表
Node *head = createTail();
int key;
scanf("%d", &key);
// 2.删除所有值为key的结点
int cnt = removeAllKey(head, key);
printf("共删除%d个结点\n", cnt);
printList(head);
// 3.释放链表
freeList(head);
return 0;
}10.单链表反转：void reverseList(Node *head);
void reverseList(Node *head)
{
Node *pre = nullptr;
Node *cur = head->next;
while (cur)
{
Node *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head->next = pre;
}
int main()
{
// 1.创建链表
Node *head = createTail();
// 2.反转链表所有结点
reverseList(head);
// 3.打印输出链表
printList(head);
// 4.释放链表
freeList(head);
return 0;
}11.合并两个有序链表（升序）：Node *mergeList(Node *h1, Node *h2);
Node *mergeList(Node *h1, Node *h2)
{
Node *head = new Node();
Node *p = head, *a = h1->next, *b = h2->next;
while (a && b)
{
if ( a->data <= b->data )
{
p->next = a;
a = a->next;
}
else
{
p->next = b;
b = b->next;
}
p = p->next;
}
p->next = a ? a : b; // 剩余部分直接接到链表尾部
h1->next = h2->next = nullptr;//原链表不再使用
return head;
}
int main()
{
// 1.创建两个有序链表
Node *head1 = createTail();
Node *head2 = createTail();
// 2.合并两个有序链表
Node *head = mergeList(head1, head2);
// head1 和 head2不再有数据
// 3.打印输出链表
printList(head);
// 4.释放链表
freeList(head);
return 0;
}12.单链表排序（冒泡排序）：void sortList(Node *head);
void bubbleSortList(Node *head)
{
if (!head->next || !head->next->next)
return;
Node *last = nullptr;
while ( head->next != last)
{
Node *p = head;
while (p->next->next != last)
{
if (p->next->data > p->next->next->data)
{
//只交换数据，不改动指针
/*
int t = p->next->data;
p->next->data = p->next->next->data;
p->next->next->data = t;
*/
swap(p->next->data, p->next->next->data);
}
p = p->next;
}
last = p->next;
}
}
int main()
{
// 1.创建两个有序链表
Node *head = createTail();
// 2.链表排序（冒泡）
bubbleSortList(head);
// 3.打印输出链表
printList(head);
// 4.释放链表
freeList(head);
return 0;
}13.单链表排序（归并排序）：static Node *mergeSortCore(Node *first);
// 内嵌递归函数：对不带头结点的子链表进行归并排序，返回排序后的首结点
static Node *mergeSortCore(Node *first)
{
if (!first || !first->next)
return first;
// 快慢指针找中点
Node *slow = first, *fast = first->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
Node *mid = slow->next;
slow->next = nullptr; // 断开
Node *left = mergeSortCore(first);
Node *right = mergeSortCore(mid);
// 合并两个有序子链表
Node dummy, *cur = &dummy;
while (left && right)
{
if (left->data <= right->data)
{
cur->next = left;
left = left->next;
}
else
{
cur->next = right;
right = right->next;
}
cur = cur->next;
}
cur->next = left ? left : right;
return dummy.next;
}
void mergeSortList(Node *head)
{
if (!head->next || !head->next->next)
return;
head->next = mergeSortCore(head->next);
}
int main()
{
// 1.创建两个有序链表
Node *head = createTail();
// 2.链表排序（冒泡）
mergeSortList(head);
编辑文章
C++单向（循环）链表操作模板
· 文章
Ctrl+K
// 3.打印输出链表
printList(head);
// 4.释放链表
freeList(head);
return 0;
}下面给出一个用类封装的单链表操作：
#include <bits/stdc++.h>
using namespace std;
// 单链表结点定义
struct Node
{
int data;
Node *next;
Node(int x = 0): data(x), next(nullptr) {};
};
class SLinkedList
{
private:
Node *head;
public:
SLinkedList()
{
head = new Node();
}
// 尾插法创建链表（用数组）
void createListTail(const int arr[], int n)
{
Node *tail = head;
for (int i = 0; i < n; i++)
{
tail->next = new Node(arr[i]);
tail = tail->next;
}
}
// 打印输出链表（横向，空格分隔）
void printList ()const
{
Node *p = head->next;
if (!p)
return;
printf("%d", p->data);
p = p->next;
while (p)
{
printf(" %d", p->data);
p = p->next;
}
printf("\n");
}
// 返回头结点
Node *getHead ()const
{
return head;
}
// 返回第 i 个结点的指针（头结点为第0个，第1个为首元结点）
Node *getAt(int i)const
{
if (i < 0)
return nullptr;
Node *p = head;
int pos = 0;
while (p && pos < i)
{
p = p->next;
pos++;
}
return p;// p 可能为 nullptr（i 越界）
}
// 查找值为 x 的结点，返回其指针，若不存在返回 nullptr
Node *findNode(int x) const
{
Node *p = head->next;
while (p)
{
if (p->data == x)
return p;
p = p->next;
}
return nullptr;
}
// 返回值为x的结点指针
Node *findPrev(int x)const
{
Node *p = head;
while (p->next)
{
if (p->next->data == x)
return p;
p = p->next;
}
return nullptr;
}
// 在p之后插入结点e
void insertAfter(Node *p, int e)
{
if (!p)
return;
Node *newNode = new Node(e);
newNode->next = p->next;
p->next = newNode;
}
// 删除p之后的结点
bool delAfter(Node *p)
{
if (!p || !p->next)
return false;
Node *q = p->next;
p->next = q->next;
delete q;
return true;
}
// 判断链表是否为空
bool isEmpty() const
{
return head->next == nullptr;
}
};
int main()
{
SLinkedList list;
int nums[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// 1.创建链表
list.createListTail(nums, 10);
// 2.打印输出链表
printf("链表：");
list.printList();
// 3. 第 i 个元素后插入 e
int i = 3, e = 99;
Node *p = list.getAt(i);
list.insertAfter(p, e);
printf("插入后：");
list.printList();
// 4.删除第 n 个元素
int n;
cout << "输出要删除元素的位置：";
cin >> n;
p = list.getAt(n - 1); //获取第n-1个元素
if (p)
list.delAfter(p);
else
cout << "删除位置无效" << endl;
printf("删除后：");
list.printList();
return 0;
}
单向循环链表
1.定义
单向循环链表是一种特殊的链表结构，其中最后一个节点的指针（或引用）不是指向空值（NULL），而是指向链表的头节点，从而形成一个环状或循环的结构。其最显著的优点是：从任一结点出发都可访问到表中所有结点，无需从头开始。
2.单向循环链表基础操作
(1)初始化。空链表仅存头结点，自身成环。
Node* head = new Node();
head->next = head;
(2)判空
bool isEmpty(Node* head)
{
return head->next == head;
}
(3)遍历。终止条件：指针回到头结点，防止死循环。
void traverse(Node* head)
{
Node* p = head->next;
while(p != head)
{
cout<val<<” “;
p = p->next;
}
}
(4)尾插法。找到尾节点（p->next==head）再插入。
void pushBack(Node* head, int x)
{
Node* p = head;
while(p->next != head) p = p->next;
Node* newNode = new Node(x);
p->next = newNode;
newNode->next = head;
}
(5)指定节点后插入。插入逻辑和普通单链表一致，仅边界闭环。
void insertAfter(Node* pos, int x)
{
Node* newNode = new Node(x);
newNode->next = pos->next;
pos->next = newNode;
}
(6)删除指定值节点。遍历找前驱，闭环重新衔接。
void delNode(Node* head, int x)
{
if(isEmpty(head)) return;
Node* p = head, *q;
while(p->next != head && p->next->val != x)
p = p->next;
if(p->next == head) return; // 无目标节点
q = p->next;
p->next = q->next;
delete q;
}
(7)清空链表。逐个释放节点，最后恢复空环。
void clear(Node* head)
{
Node* p = head->next, *q;
while(p != head)
{
q = p->next;
delete p;
p = q;
}
head->next = head;
}
单向循环链表和单向链表的区别：
(1)初始化
普通head->next=nullptr
循环head->next=head
(2)判空
普通：head->next == nullptr
循环：head->next == head
(3)遍历终止条件
普通：p != nullptr
循环：p != head
(4)尾节点判断
普通：p->next==nullptr
循环：p->next==head
下面给出类封装的单向链表操作：
#include <bits/stdc++.h>
using namespace std;
// 单链表节点
struct Node
{
int data;
Node *next;
Node(int x = 0) : data(x), next(nullptr) {}
};
// 单向链表类
class SingleLinkList
{
private:
Node *head; // 带头哑结点
public:
// 构造初始化
SingleLinkList()
{
head = new Node();
head->next = nullptr;
}
// 析构释放
~SingleLinkList()
{
clear();
delete head;
}
// 头插法批量建表
void createHead(int arr[], int n);
// 尾插法批量建表
void createTail(int arr[], int n);
// 在pos节点后方插入元素x
void insertAfter(Node *pos, int x);
// 删除指定节点
void delNode(Node *cur);
// 查找值为x的节点，找不到返回nullptr
Node *find(int x);
// 正向遍历输出
void traverse();
// 获取链表有效长度
int getLength();
// 清空所有有效节点
void clear();
// 获取头结点
Node *getHead();
};
// 头插建表
void SingleLinkList::createHead(int arr[], int n)
{
clear();
for (int i = 0; i < n; ++i)
insertAfter(head, arr[i]);
}
// 尾插建表
void SingleLinkList::createTail(int arr[], int n)
{
clear();
Node *tail = head;
for (int i = 0; i < n; ++i)
{
insertAfter(tail, arr[i]);
tail = tail->next;
}
}
// 指定节点后插入
void SingleLinkList::insertAfter(Node *pos, int x)
{
if (!pos)
return;
Node *newNode = new Node(x);
newNode->next = pos->next;
pos->next = newNode;
}
// 删除指定节点
void SingleLinkList::delNode(Node *cur)
{
if (!cur || cur == head)
return;
Node *p = head;
// 查找前驱节点
while (p && p->next != cur)
p = p->next;
if (!p)
return;
p->next = cur->next;
delete cur;
}
// 按值查找
Node *SingleLinkList::find(int x)
{
Node *p = head->next;
while (p)
{
if (p->data == x)
return p;
p = p->next;
}
return nullptr;
}
// 遍历打印
void SingleLinkList::traverse()
{
Node *p = head->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
// 统计长度
int SingleLinkList::getLength()
{
int len = 0;
Node *p = head->next;
while (p)
{
len++;
p = p->next;
}
return len;
}
// 清空链表
void SingleLinkList::clear()
{
Node *p = head->next, *q;
while (p)
{
q = p->next;
delete p;
p = q;
}
head->next = nullptr;
}
// 获取头结点
Node *SingleLinkList::getHead()
{
return head;
}
// 测试用例
int main()
{
SingleLinkList slist;
int a[] = {1, 2, 3, 4, 5};
int n = sizeof(a) / sizeof(int);
slist.createTail(a, n);
cout << "初始链表：";
slist.traverse();
cout << "链表长度：" << slist.getLength() << endl;
Node *pos = slist.find(3);
if (pos)
slist.insertAfter(pos, 6);
cout << "插入元素后：";
slist.traverse();
slist.delNode(pos);
cout << "删除节点后：";
slist.traverse();
slist.clear();
cout << "清空后长度：" << slist.getLength() << endl;
return 0;
}