C++ 链表

浮生丶若尘 2023-08-23 原文

虽然C++中有list容器，但是在某些oj题中会出现有关链表的题，所以写一篇C++链表。

省去太过官方的定义，只做最简单易懂的介绍。

链表结构

一个数据所在的内存块被分为两个部分，第一个部分放数据，而第二个部分则放下一个数据的地址，以此来连接各个数据，最后一个内存块放的地址为NULL。这样的一个内存块叫做节点。

在代码中，链表的一个节点是这样的：

struct ListNode
{
	int data;
	ListNode* next;//结构体指针
};

链表有一定的缺陷：每存放一个数据都需要伴随下一个数据的地址并且不支持随机访问。

一，单链表

先来看最简单的单链表。

1.实现基本的增删查改

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//结构体指针
};
void Listprintf(ListNode* phead)
{
	ListNode* cur=phead;
	while (cur != NULL)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
}
void Listpushback(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		ListNode* tail=  *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void test_1()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3); 
	Listprintf(phead);
}
int main()
{
	test_1();
	return 0;
}

运行结果：

在这段代码中有一些需要注意的地方，比如：

在Listpushback这个函数中，参数是二级指针，如果写成一级指针：

void Listpushback(ListNode* pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (pphead == NULL)
	{
		pphead = newnode;
	}
	else
	{
		ListNode* tail=  pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

则结果会变成：

没有任何输出。

原因是原本的指针phead是没有任何指向的，这个指针没有指向某一个地址，而是一个空指针，在函数传参的时候，如果参数pphead是一级指针，则pphead也是空指针，改变pphead，并不会影响到phead，所以最终一通操作下来，phead还是空指针，输出结果也就是空的。

下面再增加一些功能：

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//结构体指针
};
void Listprintf(ListNode* phead)
{
	ListNode* cur=phead;
	while (cur != NULL)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
	cout << "NULL" << endl;
}
//尾插
void Listpushback(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		ListNode* tail=  *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//头插
void Listpushfront(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾删
void Listpopback(ListNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	if ((*pphead)->next == NULL)
	{
		delete(*pphead);
		*pphead = NULL;
	}
	else
	{
		ListNode* tail = *pphead;
		ListNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		delete(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
//头删
void Listpopfront(ListNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		ListNode* newnode = (*pphead)->next;
		delete(*pphead);
		*pphead = newnode;
	}
}
//查找元素，返回值是地址
ListNode* Listfind(ListNode* phead, int x)
{
	ListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
//插入元素，在pos的前一个位置插入
//配合Listfind使用，具体使用见test_insert函数
void Listinsert(ListNode** phead, ListNode* pos, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*phead == pos)
	{
		newnode->next = (*phead);
		*phead = newnode;
	}
	else
	{
		ListNode* posprev = *phead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
}
//单链表并不适合在前一个位置插入，因为运算较麻烦，会损失效率
//包括c++中为单链表提供的库函数也只有一个insert_after而没有前一个位置插入
//在后一个位置插入相对简单
void Listinsert_after(ListNode** phead, ListNode* pos, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除指定位置的节点
void Listerase(ListNode** pphead, ListNode* pos)
{
	if (*pphead == pos)
	{
		*pphead = pos->next;
		delete(pos);
	}
	else
	{
		ListNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		delete(pos);
	}
}
//释放链表
void Listdestory(ListNode** pphead)
{
	ListNode* cur = *pphead;
	while(cur)
	{
		ListNode* next = cur->next;
		delete(cur);
		cur = next;
	}
	*pphead = NULL;
}
void test_insert()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	ListNode* pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		Listinsert(&phead, pos, 20);
	}
	Listprintf(phead);
	pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		Listinsert_after(&phead, pos, 20);
	}
	Listprintf(phead);
	Listdestory(&phead);
}
void test_find()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	ListNode* pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		pos->data = 20;//Listfind不仅能查找，也能借此修改，这也是函数返回地址的原因
	}
	Listprintf(phead);
	Listdestory(&phead);
}
void test_erase()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	ListNode* pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		Listerase(&phead, pos);
	}
	Listprintf(phead);
	Listdestory(&phead);
}
void test_pop_and_push()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	Listpushfront(&phead, 1);
	Listpushfront(&phead, 2);
	Listpushfront(&phead, 3);
	Listprintf(phead);
	Listpopback(&phead);
	Listpopfront(&phead);
	Listprintf(phead);
	Listdestory(&phead);
}
int main()
{
	//test_pop_and_push();
	test_find();
	//test_insert();
	//test_erase();
	return 0;
}

test_pop_and_push()测试结果：

test_find()测试结果：

test_insert()测试结果：

test_erase()测试结果：

2.对链表进行一些操作

（1）删除等于给定值的所有节点。

例如：在一条链表中删除值为6的节点。

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//结构体指针
};
void Listprintf(ListNode* phead)
{
	ListNode* cur=phead;
	while (cur != NULL)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
	cout << "NULL" << endl;
}
void Listpushback(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		ListNode* tail=  *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
ListNode* creatlist()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 9);
	Listpushback(&phead, 6);
	Listpushback(&phead, 8);
	Listpushback(&phead, 6);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	return phead;
}
ListNode* removeElements(ListNode* head, int x)
{
	ListNode* prev = NULL;
	ListNode* cur = head;
	while (cur)
	{
		if (cur->data == x)
		{
			if (cur == head)//如果第一个元素就是要删除的，进行头删
			{
				head = cur->next;
				delete(cur);
				cur = head;
			}
			else
			{
				prev->next = cur->next;
				delete(cur);
				cur = prev->next;
			}
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;
}
int main()
{
	ListNode*phead = creatlist();//先创建一条链表
	Listprintf(phead);
	phead = removeElements(phead, 6);//删除值为6的节点
	Listprintf(phead);
	return 0;
}

自测结果：

当然如果是一条全为6的链表也是可以完成删除的：

这里再说一下为什么删除元素和创建链表这两个函数的参数不是二级指针，因为这两个函数是要返回一个指针的。

（2）翻转链表

比如：将1->2->3->4->5翻转为5->4->3->2->1

翻转链表的方式很多，这里只写两种作为参考：

第一种，翻转指针。

这种方法的逻辑是定义三个指针，一个用来纪录当前位置的前一个位置，一个用来纪录当前位置，一个用来纪录当前位置的后一个位置，再通过将当前位置指向下一个位置的指针修改为指向上一个位置，再往后迭代，以达到翻转链表的目的。

为什么要三个指针呢，因为将当前位置指向前一个位置之后，就找不到当前位置的下一个位置了，所以需要第三个指针来指向下一个位置。

代码部分由于只有测试函数不一样，其余代码差异不大，所以仅贴出测试函数部分：

ListNode* reverseList(ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	ListNode* prev, * cur, * next;
	prev = NULL;
	cur = head;
	next = cur->next;
	while (cur)
	{
		cur->next = prev;//翻转指针

		//往后迭代
		prev = cur;
		cur = next;
		if (next)//这里是因为当cur指向最后一个节点的时候，next就已经是NULL了，这个时候如果再执行next=next->next则会出现错误
		{
			next = next->next;
		}
	}
	return prev;
}

自测结果：

测试结果（测试网站：牛客网）：

第二种方式，创建新链表进行头插

这种方法的逻辑是将原链表中的节点取下来头插到新链表newlist中，同样的，需要三个指针，一个为NULL，即为新链表newlist，一个纪录原链表从头开始的地址，一个纪录下一个位置。将原链表第一个节点取下来对newlist进行头插，再取第二个第三个，往后迭代。

ListNode* reverseList(ListNode* head)
{
	ListNode* cur = head;
	ListNode* newlist = NULL;
	ListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		//头插
		cur->next = newlist;
		newlist = cur;
		//往后迭代
		cur = next;
	}
	return newlist;
}

自测结果：

测试结果（测试网站：牛客网）：

（3）返回中间节点的地址

如果有两个中间节点，返回第二个中间节点。

这种操作比较简单，最容易想到的方法就是先遍历一次整个链表找出有几个节点，再遍历一次找出中间节点

但是如果要求只能遍历一次呢，所以这里不采用遍历两次的方法，而采用快慢指针的方式只遍历一次。

逻辑就是定义两个指针，一个走的更慢，一次走一步，另一个走的更快，一次走两步。

ListNode* middleNode(ListNode* head)
{
	ListNode* slow, * fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

自测结果：

（4）倒数第k个节点

输入一个链表和k，输出从倒数第k个节点到最后一个。

思路和快慢指针相似，定义两个指针，一个指针先走k步。

ListNode* findK(ListNode* head, int k)
{
	ListNode* fast, * slow;
	fast = slow = head;
	while(k--)
	{
		if (fast == NULL)//如果当fast等于NULL时k仍不为0，则k大于链表长度
		{
			return NULL;
		}
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

自测结果：

测试结果（测试网站：牛客网）：

（5）合并有序链表

思路比较简单，依次比较链表中的节点，将较小的节点尾插到新链表。

当然还有一种做法是将一个链表直接插入到另一个链表中，这种方式画图画起来倒是简单，但是实际写起来很麻烦，这里不推荐这种写法，也不会写这种。

ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{
	if (l1 == NULL)//如果一个链表为空，则返回另一个
	{
		return l2;
	}
	if (l2 == NULL)
	{
		return l1;
	}
	ListNode* head = NULL;
	ListNode* tail = NULL;
	while (l1 && l2)
	{
		if (l1->data < l2->data)
		{
			if (head == NULL)
			{
				head = tail =l1;
			}
			else
			{
				tail->next = l1;
				tail = l1;
			}
			l1 = l1->next;
		}
		else
		{
			if (head == NULL)
			{
				head = tail = l2;
			}
			else
			{
				tail->next = l2;
				tail = l2;
			}
			l2 = l2->next;
		}
	}
	if (l1)
	{
		tail->next = l1;
	}
	if(l2)
	{
		tail->next = l2;
	}
	return head;
}

自测结果：

我这里是将两条1->2->3->4->5->6的链表合并。

测试结果（测试网站：牛客网）：

可以看到这种不带哨兵位的写法也还是比较麻烦，要判断头为不为空，所以下面再写一种带哨兵位的写法。

带哨兵位（也叫带头）就是我们去给链表多定义一个头结点，这个节点不存储有效数据。

ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{
	if (l1 == NULL)//如果一个链表为空，则返回另一个
	{
		return l2;
	}
	if (l2 == NULL)
	{
		return l1;
	}
	ListNode* head = NULL, * tail = NULL;
	head = tail = new ListNode;//哨兵位的头结点
	while (l1 && l2)
	{
		if (l1->data < l2->data)
		{
		    tail->next = l1;
		    tail = l1;
		    l1 = l1->next;
	 	}
		else
		{
			tail->next = l2;
			tail = l2;
			l2 = l2->next;
		}
	}
	if (l1)
	{
		tail->next = l1;
	}
	if (l2)
	{
		tail->next = l2;
	}
	ListNode* list = head->next;
	delete(head);
	return list;
}

自测结果：

测试结果（测试网站：牛客网）：

（6）分割链表

给定一个值x，将所有小于x的节点排在其余节点之前，且不能改变原来的数据顺序，返回重新排列后的链表头指针。

思路：定义两条链表，一条将小于x的所有节点按照原顺序连接成链表，另一条将大于x的所有节点按照原顺序连接成链表，最后再合起来。

ListNode* partition(ListNode* phead, int x)
{
	ListNode* lesshead, * lesstail, * greaterhead, * greatertail;

	lesshead = lesstail = new ListNode;//定义一个哨兵位头结点，方便尾插
	lesstail->next = NULL;
	greaterhead = greatertail = new ListNode;
	greatertail->next = NULL;

	ListNode* cur = phead;
	while (cur)
	{
		if (cur->data < x)
		{
			lesstail->next = cur;
			lesstail = cur;
		}
		else
		{
			greatertail->next = cur;
			greatertail = cur;
		}
		cur = cur->next;
	}
	lesstail->next = greaterhead->next;
	greatertail->next = NULL;//举个例子，这样一条链表:1->4->15->5,现在给的x是6，那么排序后15应该在最后，正因如此，重新排序后15的next是没变的，仍然指向5，不手动将next改为NULL，就会成环，无限排下去。
	
	ListNode* newhead = lesshead->next;
	delete(lesshead);
	delete(greaterhead);
	return newhead;
}

自测结果：

测试结果（测试网站：力扣）：

（7）链表回文

判断链表是否回文。

思路，先找到一条链表的中点，将后半段逆置，设置两个指针，一个从头开始，一个从逆置后的头开始，逐个判断直到最后。

图：

节点奇数个：

节点偶数个：

代码：

ListNode* middleNode(ListNode* head)
{
	ListNode* slow, * fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
ListNode* reverseList(ListNode* head)
{
	ListNode* cur = head;
	ListNode* newlist = NULL;
	ListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		//头插
		cur->next = newlist;
		newlist = cur;
		//往后迭代
		cur = next;
	}
	return newlist;
}
bool check(ListNode* head)
{
	ListNode* mid = middleNode(head);
	ListNode* rhead = reverseList(mid);
	ListNode* curHead = head;
	ListNode* curRhead = rhead;
	while(curHead&&curRhead)
	{
		if (curHead->data != curRhead->data)
			return false;
		else
		{
			curHead = curHead->next;
			curRhead = curRhead->next;
		}
	}
	return true;
}

自测结果：

测试结果（测试网站：牛客网）：

（8）链表相交

给两个单链表的头结点，找出并返回两个单链表相交的起始节点，没有交点则返回null。

最简单粗暴的思路就是将A链表的每个节点和B链表的每个节点挨着挨着比较，这里不使用这一种。

还有一种思路就是，找到A和B的尾结点对比，如果一样则有交点，如果不一样则没有交点，有交点的情况下又该怎样找到相交的起始节点？

如果两条链表在相交之前的节点个数一样的话，那么找到相交的起始节点就很简单，定义两个指针同时向前走直到相等即可，所以我们在找链表A和B的尾结点的时候，同时纪录下A和B的长度，用长的减去短的得到一个数x，再分别为两条链表定义头指针，让长的那条链表的头指针先走x步，那么就可以当做是在相交之前节点数一样了。

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
{
        if(pHead1==NULL)
        {
            return NULL;
        }
        if(pHead2==NULL)
        {
            return NULL;
        }
        ListNode* tail1=pHead1;
        ListNode* tail2=pHead2;
        int len1=1,len2=1;
        while(tail1->next)
        {
            len1++;
            tail1=tail1->next;
        }
        while(tail2->next)
        {
            len2++;
            tail2=tail2->next;
        }
        if(tail1!=tail2)//不相交
        {
            return NULL;
        }
        int gap=abs(len1-len2);
        ListNode* longlist=pHead1;
        ListNode* shortlist=pHead2;
        if(len1<len2)
        {
            longlist=pHead2;
            shortlist=pHead1;
        }
        while(gap--)//长的先走差距步，再同时走找交点
        {
            longlist=longlist->next;
        }
        while(longlist!=shortlist)
        {
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
        return longlist;
    }

测试结果（测试网站：牛客网）：

（9）环形链表

判断链表是否带环，并且返回环的入口节点。

判断是否带环的思路比较简单，定义两个指针，一个走得快，一次走两步，一个走得慢，一次走一步，如果不带环，那么走得快的最终会走到NULL，如果带环，那么走得快的会和走得慢的相遇。

要找环的入口节点，也需要定义两个指针，一个从链表头开始，一个从快慢指针相遇的位置开始，他们同时出发，当这两个指针相遇时，所在的位置就是入口节点。

这里做简单的证明，假设链表头到入口节点距离是L，快慢指针相遇的位置meetnode距离入口节点为x

假设C是环的长度，当快慢指针相遇时，快指针走的距离是L+N*C+x，N是快指针走的圈数，慢指针走的距离是L+x，因为快指针一次走两步，慢指针一次走一步，所以快指针走的距离是慢指针的两倍，所以有：

L+N*C+x=2（L+x）

得到：

L+x=N*C

L=（N-1）*C+C-x

其中C-x即为meetnode到入口节点的距离，所以当头指针和从meetnode出发的指针相遇时，头指针走了L，从meetnode出发的指针走了C-x，相遇点即为入口节点。

代码：

ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode*fast=pHead;
        ListNode*slow=pHead;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow)
            {
                ListNode*meet=fast;
                while(meet!=pHead)
                {
                    meet=meet->next;
                    pHead=pHead->next;
                }
                return pHead;
            }
        }
        return NULL;
    }

测试结果（测试网站：牛客网）：

这里再说下还有另一种处理方式，就是将meetnode作为链表的尾，meetnode的next作为链表的头，就转化成了两条相交链表找第一个相交节点的问题，这种方式写起来会麻烦一些，这里也不做代码实现。

二，双向链表

双向链表的一个数据所在的内存块是被分成了三部分，除了像单链表那样一部分存储数据，一部分存储下一个数据的地址之外，还要有一部分来存储上一个数据的地址。

在代码中如下：

struct ListNode
{
	int data;
	ListNode* next;//结构体指针
	ListNode* prev;
};

双向链表的结构：

其中最常用的是双向带头（哨兵位）循环链表

后面的代码中双向链表也都是这种。

1.增删查改

这里多说一句，很多人都会下意识的认为在带哨兵位的链表中，哨兵位是一条链表开始的位置，但是实际上哨兵位的下一位才是。

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//结构体指针
	ListNode* prev;
};
ListNode* Initlist()//初始化双向带头（哨兵）循环链表
{
	ListNode* phead=new ListNode;
	phead->next = phead;
	phead->prev = phead;//定义一个哨兵位，自己的next和prev指向自己
	return phead;
}
void pushback(ListNode* phead,int x)//尾插
{
	ListNode* tail = phead->prev;//循环链表，哨兵位的前一个就是尾
	ListNode* newhead = new ListNode;
	newhead->data = x;

	newhead->next = phead;
	newhead->prev = tail;
	tail->next = newhead;
	phead->prev = newhead;
}
void popback(ListNode* phead)//尾删
{
	if (phead->next == phead)//链表为空，不能再删了
		return;

	ListNode* tail = phead->prev;
	ListNode* tailprev = tail->prev;

	tailprev->next = phead;
	phead->prev = tailprev;

	delete(tail);
}
void pushfront(ListNode* phead,int x)//头插
{
	ListNode* next = phead->next;
	ListNode* newnode = new ListNode;
	newnode->data = x;

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}
void popfront(ListNode* phead)//头删
{
	if (phead->next == phead)//链表为空，不能再删了
		return;

	ListNode* next = phead->next;
	ListNode* dnext = next->next;

	phead->next = dnext;
	dnext->prev = phead;

	delete(next);
}
ListNode* listFind(ListNode* phead, int x)//查找
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
void insertList(ListNode* pos, int x)//指定位置插入
{
	ListNode* prev = pos->prev;
	ListNode* newnode = new ListNode;
	newnode->data = x;

	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
void eraseList(ListNode* pos)//指定位置删除
{
	ListNode* posNext = pos->next;
	ListNode* posPrev = pos->prev;

	posNext->prev = posPrev;
	posPrev->next = posNext;
	delete(pos);
	pos = NULL;
}
void printlist(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}
void test_pop_push()
{
	ListNode* phead = Initlist();
	pushback(phead, 1);
	pushback(phead, 2);
	pushback(phead, 3);
	printlist(phead);
	popback(phead);
	popback(phead);
	printlist(phead);
	pushfront(phead, 1);
	pushfront(phead, 2);
	pushfront(phead, 3);
	printlist(phead);
	popfront(phead);
	popfront(phead);
	printlist(phead);
}
void test_find_insert_erase()
{
	ListNode* phead = Initlist();
	pushback(phead, 1);
	pushback(phead, 2);
	pushback(phead, 3);
	printlist(phead);
	ListNode* p = listFind(phead, 2);
	insertList(p, 20);
	printlist(phead);
	p = listFind(phead, 20);
	eraseList(p);
	printlist(phead);
}
int main()
{
	//test_pop_push();
	test_find_insert_erase();
	return 0;
}

test_pop_push()测试结果：

test_find_insert_erase()测试结果：

其中最重要的是insert()和erase()函数，在双向带头循环链表中，这两个函数是可以分别和头尾插，头尾删函数复用的，即可以修改成：

void pushback(ListNode* phead,int x)//尾插
{
	insertList(phead,x);
}
void popback(ListNode* phead)//尾删
{
	if (phead->next == phead)//链表为空，不能再删了
		return;

	eraseList(phead->prev);
}
void pushfront(ListNode* phead,int x)//头插
{
	insertList(phead->next, x);
}
void popfront(ListNode* phead)//头删
{
	if (phead->next == phead)//链表为空，不能再删了
		return;

	eraseList(phead->next);
}

最后再说一下为什么双向链表中的函数的参数是一级指针而不是像之前单链表那样是二级指针的问题，这是因为在我写的双向链表中是带了头的，也就是带了哨兵位，所以不需要考虑传进来的是空指针，改变形参不会影响变量的问题，而在我写单链表的时候是没有带头的。

C++链表 ListNode xff xff0c 学习散列表

有关C++ 链表的更多相关文章

【数据结构和算法】实现带头双向循环链表（最复杂的链表） - 2
前文，我们实现了认识了链表这一结构，并实现了无头单向非循环链表，接下来我们实现另一种常用的链表结构，带头双向循环链表。如有仍不了解单向链表的，请看这一篇文章(7条消息)【数据结构和算法】认识线性表中的链表，并实现单向链表_小王学代码的博客-CSDN博客目录前言一、带头双向循环链表是什么？二、实现带头双向循环链表1.结构体和要实现函数2.初始化和打印链表3.头插和尾插4.头删和尾删5.查找和返回结点个数6.在pos位置之前插入结点7.删除指定pos结点8.摧毁链表三、完整代码1.DSLinkList.h2.DSLinkList.c3.test.c总结前言带头双向循环链表，是链表中最为复杂的一种结
ruby - Ruby 有像栈、队列、链表、映射或集合这样的容器吗？ - 2
我在网上查了几个Ruby教程，他们似乎什么都用数组。那么如何在Ruby中实现以下数据结构呢？堆栈队列链表map组最佳答案 (从评论中移出)好吧，通过限制堆栈或队列方法(push、pop、shift、unshift)，数组可以是堆栈或队列。使用push/pop提供LIFO(后进先出)行为(堆栈)，而使用push/shift或unshift/pop提供FIFO行为(队列)。map是hashes,和一个Set类已经存在。您可以使用类实现链表，但数组将使用标准数组方法提供类似于链表的行为。关
javascript - JS将数组转换为json链表？ - 2
我是JS的新手，组织数据的概念让我有些困惑，我试图从特定的数组格式中获取数据(因为这是我必须使用的格式)并将其输出为另一种特定的JSON格式。这是给D3sankey模块传递数据https://github.com/d3/d3-plugins/blob/master/sankey/sankey.js我不知道如何将节点的索引添加到链接中，而不是名称。真的，我完全迷失了它!我在这里做了一个fiddle:https://jsfiddle.net/adamdavi3s/kw3jtzx4/下面是所需数据和输出的示例vardata=[{"source":"Agricultural'waste'","
合并两个有序链表 - 2
文章目录1.题目描述2.解题思路方法1：方法2：1.题目描述题目链接：力扣21，合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。2.解题思路方法1：首先我们能够想到的就是遍历一遍数组，判断两个结点的大小，将数值小的结点放在前面，数值大的不断尾插在后面。是不是听着挺简单的？具体实现：我们可以创建两个空指针，head用来存放链表的头结点，tail用来遍历两条链表，将两条链表链接起来。当某个链表为空时，我们可以直接返回另一条链表当两个链表都不为空时，我们可以不断比较两条链表的大小，当head和tail为空时，我们将较小的结点同时赋给head
javascript - Javascript 中的链表与数组 - 2
所以我在JS中玩弄链表并提出了以下问题:比方说，我们有一个数组和一个链表，它们都有5000个元素。我们想在索引10处插入新元素。数组方式非常简单。我们在给定索引处插入新元素，并将其余元素向前移动一个索引。所以我尝试用链表来做这件事，并以下面的方式结束它:从NicholasZakas获取链表的实现并添加附加方法addOnPosition(data,index)。最后是代码:functionLinkedList(){this._head=null;this._length=0;}LinkedList.prototype={constructor:LinkedList,add:functio
【数据结构与算法】一套链表 OJ 带你轻松玩转链表 - 2
✨个人主页：bitme✨当前专栏：数据结构✨刷题专栏：基础算法链表OJ🏳️一.移除链表元素🏴二.反转链表🏁三.链表的中间结点🚩四.链表中倒数第k个结点🏳️‍🌈五.合并两个有序链表🏳️‍⚧️六.链表的回文结构🏴‍☠️七.链表分割🏴󠁧󠁢󠁷󠁬󠁳󠁿八.相交链表🏳️‍🌈九.环形链表🍹十.环形链表II 🏳️一.移除链表元素简介：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val==val的节点，并返回新的头节点。示例1：输入：head=[1,2,6,3,4,5,6],val=6输出：[1,2,3,4,5]示例2：输入：head=[],val=1输出：[]示例3：输入：he
go - 输出反向链表时出现无限循环 - 2
我正在学习Go并编写了以下代码来反转链表。但是，代码没有按预期工作。这是一个节点结构以及用于打印和反转列表的函数。typeNodestruct{numberintprevious*Nodenext*Node}funcPrintList(node*Node){forn:=node;n!=nil;n=n.next{fmt.Println(n)}}funcReverseList(node*Node){varnextNodeRef*Nodeforn:=node;n!=nil;n=n.previous{ifn.next==nil{n.next=n.previousn.previous=nil*n
C语言实现链表--数据结构 - 2
魔王的介绍：😶‍🌫️一名双非本科大一小白。魔王的目标：🤯努力赶上周围卷王的脚步。魔王的主页：🔥🔥🔥大魔王.🔥🔥🔥❤️‍🔥大魔王与你分享：很喜欢宫崎骏说的一句话:“不要轻易去依赖一个人,它会成为你的习惯当分别来临,你失去的不是某个人而是你精神的支柱,无论何时何地,都要学会独立行走,它会让你走得更坦然些。”文章目录一、前言二、链表实现1、创建结构体类型2、创建结点3、打印单链表4、单链表尾插5、单链表头插6、单链表尾删7、单链表头删8、单链表查找9、单链表插入☃️该位置之后插入☃️该位置之前插入（插入正常理解）10、单链表删除11、单链表销毁三、总代码SeqListNode.hSeqListNod
go - 一个结构体的单向链表的初始化 - 2
对于我正在处理的一项任务，我们被指示创建两个实现Stack接口(interface)(包括push、pop等方法)的数据结构。当我完成第一个结构时，链表部分让我不知所措。作为正在编写他们的第一个Go项目的人，我不确定如何处理以下指令:1.创建一个名为StackLinked的新结构，它实现了Stacker，并使用单(或双)链表作为其内部表示。2.除了实现Stacker中的所有方法外，还编写一个makeStackLinked()函数(不是方法!)，该函数使用链表表示返回一个新的空堆栈我曾尝试这样实现:typeStackLinkedstruct{top*StackLinkednext*Sta
go - 链表在 Golang 中不会改变 - 2
我的问题是，当我将head指向head.next时input.Val仍然是1而不是2(这是下一个值)。typeListNodestruct{ValintNext*ListNode}functest(head*ListNode)*ListNode{head=head.Nextreturnhead}funcmain(){varinput,input2ListNodeinput=ListNode{Val:1,Next:&input2}}input2=ListNode{Val:2}test(&input)fmt.Println(input.Val)} 最佳答案

C++ 链表

链表结构

一，单链表

1.实现基本的增删查改

2.对链表进行一些操作

（1）删除等于给定值的所有节点。

（2）翻转链表

（3） 返回中间节点的地址

（4）倒数第k个节点

（5）合并有序链表

（6）分割链表

（7）链表回文

（8）链表相交

（9）环形链表

二，双向链表

1.增删查改

有关C++ 链表的更多相关文章

随机推荐

（3）返回中间节点的地址