精华内容
下载资源
问答
  • c++链表
    2021-12-09 13:32:22

    链表是一种物理存储单元上不连续的存储结构,数组元素之间通过链表中的指针进行链接。链表是由一系列的结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

    每个结点包含两部分,一个是存储数据的数据域,另一个是存储下一结点地址的指针域。

    链表允许在任意位置插入或删除结点,但是不支持随机访问结点,只能从头结点逐个访问每个结点。一般在一些需要快速插入或删除,而不太关心或者不需要随机访问的情况下使用。

    #include <iostream>
    using namespace std;
    //用结构体类型来表示一个结点
    typedef struct node
    {
        //数据域
        char name[20];
        int age;
        //指针域
        struct node* next;
    }student;

    //typedef是重命名,下面申明结点时不用写struct node,而用student代替
    //创建链表
    student * createlist(int n)//n表示结点个数
    {
        student* head = new student;//头结点,动态,存在堆上
        //一般头结点不存储数据
        //student head;//存在栈上,用于函数内部,所以一般情况下,结点都是动态生成
        student* pre = head;//pre用来记录上一个结点
        //利用for 循环构建结点
        for (int i = 0; i < n; i++)
        {
            student* p = new student;
            cin >> p->name >> p->age;
            pre->next = p;
            pre = p;
            p->next = NULL;
        }
        return head;
    }
    void display(student* head)
    {
        student* p = head->next;//p为第一个结点
        while (p!=NULL)
        {
            cout << p->name << " " << p->age<<endl;
            p = p->next;
        }
    }
    int main()
    {
        int n = 5;
        student *head=createlist(n);
        display(head);
        return 0;
    }

    更多相关内容
  • C++ 链表

    千次阅读 2022-06-07 17:15:18
    C++链表笔记

    目录

    链表结构

    一,单链表

    1.实现基本的增删查改

     2.对链表进行一些操作

    (1)删除等于给定值的所有节点。

    (2)翻转链表

    (3) 返回中间节点的地址

    (4)倒数第k个节点 

     (5)合并有序链表

     (6)分割链表

    (7)链表回文

    (8)链表相交 

     (9)环形链表

    二,双向链表

    1.增删查改


    虽然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++链表倒序实现方法

    2021-01-20 05:30:24
    首先,C++链表倒序的难点在于如何一个个地修改。虽然不是数组,但是大概思想是一样的,所以可以用一个for循序,一个游标对应for循环里面的 i,只不过要记得前一个节点和后一个节点,尤其是后一个,因为修改之后就...
  • 使用C++实现双向循环链表的增删改查排序等操作,可查看个人博客的【[数据结构和算法]C/C++双向循环链表实现(增删改查排序)】--链接https://blog.csdn.net/slimmm/article/details/84317806
  • c++ 链表

    千次阅读 2021-10-03 12:02:35
    1.单链表, 2.循环链表 3. 双链表

    链表每一个节点都是由数据域和指针域构成的,每一个指针域指向下一个节点,每个节点的数据域存储相应的数据,

    两点除外

    1)头节点,一般头节点不存储任何数据,但也可以用来存储表长等信息

    2)最后一个节点的指针域指向NULL,即空,表示链表结束

    特点:

    1. 访问单链表中任何一个元素都必须通过头结点层层往下遍历,因此头节点是链表中最重要的节点,没有头节点就无法访问整个链表。这也是链表和顺序表最大的不同。

    2. 链表则可以动态改变长度,加之指针的方式使得其遍历速度极为高效,其灵活性和可靠性使得链表成为线性表的主要实现方式,也是栈和队列等重要数据结构类型的基础。

    备注: 顺序表是数组实现,访问节点以及返回表长都很容易实现,但是顺序表没有动态分配空间的功能,只能一开始初始化一个较大的空间以便以后利用,一旦填满,则顺序表不能再插入元素。

    1.单链表

    一个完整的单链表如下图:

    单链表的数据元素插入原理:

     若要在第i个位置上插入数据,则需要遍历单链表到第i-1个位置,然后利用malloc()函数向系统请求空间开辟新节点T

            1.先使得T的指针域 指向 第i-1个数据的指针域指向的位置(即第i个元素);

            2.再让第i-1个数据的指针域 指向 T;

            3.以上两步千万不能颠倒顺序,否则将使得整个链表丢失i位置后的所有数据元素

                        

    单链表的数据元素删除原理:

     若要删除第i个位置上的数据,也需遍历到第i-1个位置,然后利用malloc()函数向系统请求开辟新节点P

            1.P的指针域 指向 第i-1的指针域指向的位置(即第i个元素);

            2.第i-1个元素指针域 指向 第i个元素的指针域指向的位置(即第i+1个元素);

            3.释放P节点占用的空间(即删除了第i个节点);

    还有一些其他的操作,比如获得某个位置上的节点,返回单链表长度,清空/销毁链表,遍历整个链表,都是简单的方法,理解了指针就不难写,原理在此不提,关于单链表的代码,就在这里放出一段简单的实例:

    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
     
    typedef struct Node
    {
        int data;
        struct Node *next;
    }*LinkedList,LNode;
     
    void CreatLinkedList(LinkedList &L,int n)   //尾插法创建单链表;
    {
        L = (LinkedList)malloc(sizeof(LNode));  //初始化;
        L->next = NULL;
        L->data = 0;
        LinkedList Tail = L;    //尾指针;
        cout<<"Enter "<<n<<" number(s)"<<endl;
        for(int i = 0 ; i < n; i++)
        {
            LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
            cin>>Temp->data;
            Tail->next = Temp;
            Tail = Temp;
            Temp = NULL;
            L->data++;  //计数;
        }
        Tail->next = NULL;
    }
     
    bool GetElem(int &e,int i,LinkedList L) //获取结点;
    {
        while(L != NULL && i > 0)
        {
            i--;
            L = L->next;
        }
        if(i == 0 && L != NULL) //i=1时也有可能同时满足退出while的条件;
        {
            e = L->data;
            return true;
        }
        else return false;
    }
     
    bool InsertElem(int e,int i,LinkedList L)   //插入结点;
    {
        if(i > L->data+1 || i < 1)    return false;
        else
        {
            L->data++;
            while(i > 1)
            {
                i--;
                L = L -> next;
            }
            LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
            Temp->data = e;
            Temp->next = L->next;
            L->next = Temp;
            Temp = NULL;
            return true;
        }
    }
     
    bool DeleteElem(int i,LinkedList L) //删除结点;
    {
        if(i > L->data || i < 1)    return false;
        else
        {
            L->data--;
            while(i > 1)
            {
                i--;
                L = L->next;
            }
            LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
            Temp = L->next;
            L->next = Temp->next;
            free(Temp);
            Temp = NULL;
            return true;
        }
    }
     
    bool DestoryLinkedList(LinkedList &L)   //销毁单链表;
    {
        if(L->next != NULL)
            DestoryLinkedList(L->next);
        free(L);
        L = NULL;
        return true;
    }
     
    bool ClearLinkedList(LinkedList &L) //清空单链表;
    {
        DestoryLinkedList(L->next);
        L->next = NULL;
        L->data = 0;
        return true;
    }
     
    void GetLinkedList(LinkedList L)    //遍历单链表;
    {
        LinkedList Head = L->next;
        while(Head != NULL)
        {
            cout<<Head->data<<endl;
            Head = Head->next;
        }
    }
     
    int main()
    {
        int n,i,Elem;
        bool Flag;
        LinkedList L;
        cout<<"How many Elem(s) do you want to creat?"<<endl;
        cin>>n;
        CreatLinkedList(L,n);
        cout<<"Here is what they look like:"<<endl;
        GetLinkedList(L);
        cout<<"Which position of Elem do you want?"<<endl;
        cin>>i;
        Flag = GetElem(Elem,i,L);
        if(Flag == true)
            cout<<Elem<<endl;
        else
            cout<<"No maching Elem"<<endl;
        cout<<"What Elem you wanna insert , and where?"<<endl;
        cout<<"Elem :";
        cin >>Elem;
        cout<<"Position :";
        cin>>i;
        Flag = InsertElem(Elem,i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        cout<<"Which position of Elem do you want to delete :"<<endl;
        cin>>i;
        Flag = DeleteElem(i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        if(ClearLinkedList(L))   cout<<"LinkedListed Cleared!"<<endl;
        GetLinkedList(L);   //验证是否清空;
        if(DestoryLinkedList(L))    cout<<"LinkedList Destoryed!"<<endl;
        if(L == NULL) cout<<"Check"<<endl; //验证是否销毁;
        return 0;
    }

    2.循环链表

    和单链表极其相似的一种结构就是循环链表了,它的节点结构和单链表一模一样,唯一的区别就是它最后一个数据元素不指向NULL,而是指向头指针,这样的链表构成了一个环,因此成为循环链表。

     一个完整的循环链表如下图:

     循环链表的操作和单链表基本一致,差别仅在于算法中的循环条件不是L或L->为空,而是它们是否等于头指针,因为当循环到头指针,说明链表已经完整遍历一次,下面给出代码:

    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
     
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }*CircleLinkedList,LNode;
     
    void CreatLinkedList(CircleLinkedList &L,int n)   //尾插法创建循环链表;
    {
        L = (CircleLinkedList)malloc(sizeof(LNode));  //初始化;
        L->next = NULL;
        L->data = 0;
        CircleLinkedList Tail = L;    //尾指针;
        cout<<"Enter "<<n<<" number(s)"<<endl;
        for(int i = 0 ; i < n; i++)
        {
            CircleLinkedList Temp = (CircleLinkedList)malloc(sizeof(LNode));
            cin>>Temp->data;
            Tail->next = Temp;
            Tail = Temp;
            L->data++;
        }
        Tail->next = L;
    }
     
    bool GetElem(int &e,int i,CircleLinkedList L) //获取结点;
    {
        CircleLinkedList Head = L;
        while(L->next != Head && i > 0)
        {
            i--;
            L = L->next;
        }
        if(i == 0 && L != Head) //i=1时也有可能同时满足退出while的条件;
        {
            e = L->data;
            return true;
        }
        else return false;
    }
     
    bool InsertElem(int e,int i,CircleLinkedList L)   //插入结点;
    {
        if(i > L->data+1 || i < 1)    return false;
        else
        {
            L->data++;
            while(i > 1)
            {
                i--;
                L = L -> next;
            }
            CircleLinkedList Temp = (CircleLinkedList)malloc(sizeof(LNode));
            Temp->data = e;
            Temp->next = L->next;
            L->next = Temp;
            return true;
        }
    }
     
    bool DeleteElem(int i,CircleLinkedList L) //删除结点;
    {
        if(i > L->data || i < 1)    return false;
        else
        {
            L->data--;
            while(i > 1)
            {
                i--;
                L = L->next;
            }
            CircleLinkedList Temp = (CircleLinkedList)malloc(sizeof(LNode));
            Temp = L->next;
            L->next = Temp->next;
            free(Temp);
            Temp = NULL;
            return true;
        }
    }
     
    bool DestoryCircleLinkedList(CircleLinkedList &L,CircleLinkedList Head)    //销毁循环链表;
    {
        if(L->next != Head)
            DestoryCircleLinkedList(L->next,Head);
        free(L);
        L = NULL;
        return true;
    }
     
    bool ClearCircleLinkedList(CircleLinkedList &L,CircleLinkedList Head)   //清空循环链表;
    {
        DestoryCircleLinkedList(L->next,Head);
        L->next = Head;
        L->data = 0;
        return true;
    }
     
    void GetCircleLinkedList(CircleLinkedList L)    //遍历循环链表;
    {
        CircleLinkedList Head = L;
        L = L->next;
        while(L != Head)
        {
            cout<<L->data<<endl;
            L = L->next;
        }
    }
     
    int main()
    {
        int n,i,Elem;
        bool Flag;
        CircleLinkedList L;
        cout<<"How many Elem(s) do you want to creat?"<<endl;
        cin >>n;
        CreatLinkedList(L,n);
        cout<<"Here is what they look like:"<<endl;
        GetCircleLinkedList(L);
        cout<<"Which position of Elem do you want?"<<endl;
        cin >>i;
        Flag = GetElem(Elem,i,L);
        if(Flag == true)
            cout<<Elem<<endl;
        else
            cout<<"No maching Elem"<<endl;
        cout<<"What Elem you wanna insert , and where?"<<endl;
        cout<<"Elem :";
        cin>>Elem;
        cout<<"Position :";
        cin>>i;
        Flag = InsertElem(Elem,i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetCircleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        cout<<"Which position of Elem do you want to delete :"<<endl;
        cin>>i;
        Flag = DeleteElem(i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetCircleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        if(ClearCircleLinkedList(L,L))   cout<<"CircleLinkedListed Cleared!"<<endl;
        GetCircleLinkedList(L);   //验证是否清空;
        if(DestoryCircleLinkedList(L,L))    cout<<"CircleLinkedList Destoryed!"<<endl;
        if(L == NULL) cout<<"Check"<<endl;    //验证是否销毁;
        return 0;
    }

    3. 双链表

    由于单链表仅具有单向性的特点,我们引入了双向链表来克服这个缺点,顾名思义,双向链表就是能通过当前节点访问下一个/上一个节点的链表结构。

      一个完整的双向链表:

    注:上图中方便起见,将最后一个节点指向NULL,实际上可以指向一个尾指针,这里可以灵活修改

        双向链表的数据元素插入原理:

      若想在第i个位置上插入数据,则先遍历到第i-1个位置,使用malloc()函数向系统请求一个新节点T

            1.让T->pre 指向 第i-1个节点;

            2.让T->next 指向 第i-1个结点的下一个节点(即第i个节点);

            3.让i->next 指向 T;

            4.让i->pre指向T;(前提是第i个节点非空)

      双向链表的数据元素删除原理:

          若想在第i个位置上插入数据,则先遍历到第i-1个位置,使用malloc()函数向系统请求一个新节点P,且让P指向第i个数据

                1.让P->next->pre 指向 P->pre;(前提是第i+1个节点非空)

                2.让i->next 指向 p->next;

                3.释放P节点所占用的空间;(即删除了第i个节点)

    放出一段双向链表代码实例:

    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
     
    typedef struct LNode
    {
        int data;
        struct LNode *pre;
        struct LNode *next;
    }*DoubleLinkedList,LNode;
     
    void CreatDoubleLinkedList(DoubleLinkedList &L,int n)   //尾插法创建双链表;
    {
        L = (DoubleLinkedList)malloc(sizeof(LNode));
        L->pre = NULL;
        L->next = NULL;
        L->data = 0;
        DoubleLinkedList Tail = L;
        cout<<"Enter "<<n<<" Elem(s) :"<<endl;
        for(int i = 0; i < n; i++)
        {
            DoubleLinkedList Temp = (DoubleLinkedList)malloc(sizeof(LNode));
            cin>>Temp->data;
            Tail->next = Temp;
            Temp->pre = Tail;
            Tail = Temp;
            L->data++;
        }
        Tail->next = NULL;
    }
     
    bool GetElem(int &e,int i,DoubleLinkedList L)   //获取结点;
    {
        while(L != NULL && i > 0)
        {
            i--;
            L = L->next;
        }
        if(i == 0 && L != NULL)
        {
            e = L->data;
            return true;
        }
        else return false;
    }
     
    bool InsertElem(int e,int i,DoubleLinkedList L)    //插入结点;
    {
        if(i > L->data+1 || i < 1)
            return false;
        else
        {
            L->data++;
            while(i > 1)
            {
                L = L->next;
                i--;
            }
            DoubleLinkedList Temp = (DoubleLinkedList)malloc(sizeof(LNode));
            Temp->data = e;
            if(L->next != NULL)
            {
                Temp->next = L->next;
                Temp->pre = L;
                L->next->pre = Temp;
                L->next = Temp;
            }
            else
            {
                Temp->pre = L;
                L->next = Temp;
                Temp->next = NULL;
            }
        }
    }
     
    bool DeleteElem(int i,DoubleLinkedList L)   //删除结点;
    {
        if(i > L->data || i < 1)
            return false;
        else
        {
            L->data--;
            while(i > 1)
            {
                L = L->next;
                i--;
            }
            DoubleLinkedList Temp = (DoubleLinkedList)malloc(sizeof(LNode));
            Temp = L->next;
            if(L->next->next != NULL)
            {
                L->next->next->pre = L;
                L->next = L->next->next;
            }
            else
                L->next = NULL;
            free(Temp);
            Temp = NULL;
            return true;
        }
    }
     
    bool DestoryDoubleLinkedList(DoubleLinkedList &L)   //销毁双链表;
    {
        if(L->next != NULL)
            DestoryDoubleLinkedList(L->next);
        free(L);
        L = NULL;
        return true;
    }
     
    bool ClearDoubleLinkedList(DoubleLinkedList &L)     //清空双链表;
    {
        DestoryDoubleLinkedList(L->next);
        L->next = NULL;
        L->data = 0;
        return true;
    }
     
    void GetDoubleLinkedList(DoubleLinkedList L)    //遍历单链表;
    {
        DoubleLinkedList Head = L->next;
        while(Head != NULL)
        {
            cout<<Head->data<<endl;
            Head = Head->next;
        }
    }
     
    int main()
    {
        int n,i,Elem;
        bool Flag;
        DoubleLinkedList L;
        cout<<"How many Elem(s) do you want to creat?"<<endl;
        cin>>n;
        CreatDoubleLinkedList(L,n);
        cout<<"Here is what they look like:"<<endl;
        GetDoubleLinkedList(L);
        cout<<"Which position of Elem do you want?"<<endl;
        cin>>i;
        Flag = GetElem(Elem,i,L);
        if(Flag == true)
            cout<<Elem<<endl;
        else
            cout<<"No maching Elem"<<endl;
        cout<<"What Elem you wanna insert , and where?"<<endl;
        cout<<"Elem :";
        cin>>Elem;
        cout<<"Position :";
        cin>>i;
        Flag = InsertElem(Elem,i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetDoubleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        cout<<"Which position of Elem do you want to delete :"<<endl;
        cin>>i;
        Flag = DeleteElem(i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetDoubleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        if(ClearDoubleLinkedList(L))   cout<<"DoubleLinkedListed Cleared!"<<endl;
        GetDoubleLinkedList(L); //验证是否清空;
        if(DestoryDoubleLinkedList(L))    cout<<"DoubleLinkedList Destoryed!"<<endl;
        if(L == NULL)   cout<<"Check"<<endl;    //验证是否销毁;
        return 0;
    }

    特点:

        1.由于双链表具有双向性,它自然也就有单向性,因此它的清空和删除和单链表完全一致;

        2.循环链表清空删除和单链表不一致,主要体现在二者“空”状态不一致,可见上图;

        3.这里声明的变量:LinkedList a;     a是该结构体类型指针型的变量,见下面定义

    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }*LinkedList;

         4.关于free()函数,它只能释放由calloc(),malloc(),realloc()申请的动态空间,不可以释放用户自定义的空间,若把上面代码的清空单链表函数改为如下,则相当于没有清空,对单链表没任何影响,我看许多人都犯这个错误,特地写一下:

    bool free_list(LinkedList head)
    {
    	LinkedList pointer;
    	while(head != NULL)
    	{
    		pointer = head;
    		head = head->next;
    		free(pointer);
    	}
            return true;
    }

    展开全文
  • c++链表的反转

    2019-09-04 22:49:33
    c++链表的反转,创建链表,插入链表,链表反转,可下载直接运行。
  • C++ 链表操作

    千次阅读 2022-05-01 18:58:45
    链表操作

    目录

    1.get(int index) 搜索索引index处的值

    2.addAthead(int val) 在表头添加节点

    3.addAttail(int val)尾部添加节点

    4.addAtindex(int index,int val) 在索引处添加值

    5.deleteAtval(int val) 删除某个节点

    6.deleteAtindex(int index) 删除索引处的值

    7.printLinklist() 打印链表

    8.reverse_listnode()翻转链表


    1.get(int index) 搜索索引index处的值

        int get(int index)
        {
            if(index<0 && index>size-1)
            {
                return -1;
            } 
            ListNode*cur=vir_node->next;
            while (index--)//往下搜寻index次
            {
                cur=cur->next;
            }
            return cur->val;
            
        } 

    2.addAthead(int val) 在表头添加节点

       void addAthead(int val)
        {
            ListNode* newnode=new ListNode(val);
            newnode->next=vir_node->next;
            vir_node->next=newnode;
            size++;
        }

    3.addAttail(int val)尾部添加节点

    void addAttail(int val)
        {
            ListNode* new_node=new ListNode(val);
            ListNode* cur=vir_node;
            while (cur->next!=nullptr)
            {
                cur=cur->next;
            }
            cur->next=new_node;
            size++;
        }

    4.addAtindex(int index,int val) 在索引处添加值

        void addAtindex(int index,int val)
        {
            if(index>size)
            {
                return;
            }
            ListNode* new_node=new ListNode(val);
            ListNode* cur=vir_node;
            while (index--)
            {
                cur=cur->next;
            }
            new_node->next=cur->next;
            cur->next=new_node;
            size++;    
        }

    5.deleteAtval(int val) 删除某个节点

      void deleteAtval(int val)
        {
            ListNode* cur=vir_node;
            while (cur->next!=NULL)
            {
                if(cur->next->val==val)
                {
                    ListNode* tmp=cur->next;
                    cur->next=cur->next->next;
                    delete tmp;
                    size--;
                }
                cur=cur->next;
            }
            
        }

    6.deleteAtindex(int index) 删除索引处的值

        void deleteAtindex(int index)
        {
            if(index>=size|| index<0)
            return;
            ListNode*cur=vir_node;
            while (index--)
            {
                cur=cur->next;
            }
            ListNode*tmp =cur->next;
            cur->next=cur->next->next;
            delete tmp;
            size--;
        }

    7.printLinklist() 打印链表

    void printLinklist()
        {
            ListNode* cur=vir_node;
            while (cur->next!=nullptr)
            {
                cout<<cur->next->val<<' ';
                cur=cur->next;
            }
            
        }

    8.reverse_listnode()翻转链表

    //循环方式翻转链表
      void reverse_listnode()
        {
        ListNode* head=vir_node->next;
        ListNode* cur=head;
        ListNode*tmp;
        ListNode*pre=NULL;
        while (cur)
        {
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
            cout<<"翻转后: "<<endl;
            while(pre!=nullptr)
            {
                cout<<pre->val<<' ';
                pre=pre->next;
            }
    
        
    }
    //递归方式翻转链表
       /*ListNode* reverse_listnode_2(ListNode* pre,ListNode* cur){
            if(cur == NULL) return pre;
            ListNode* temp = cur->next;
            cur->next = pre;
    
            return reverse_listnode_2(cur,temp);
        }
    
        void reverseList(ListNode* head) 
        {
             reverse_listnode_2(NULL, head);
        }*/

     总代码:包括节点初始化等。

    #include <iostream>
    #include <string.h>
    using namespace std;
    
    class Mylink_list
    {
        public:
        struct ListNode
        {
        int val;
        ListNode *next;
        ListNode(int x):val(x),next(NULL){}
        };
        Mylink_list()
        {
            vir_node= new ListNode(0);
            size=0;
    
        }
        int get(int index)
        {
            if(index<0 && index>size-1)
            {
                return -1;
            } 
            ListNode*cur=vir_node->next;
            while (index--)//往下搜寻index次
            {
                cur=cur->next;
            }
            return cur->val;
            
        } 
        void addAthead(int val)
        {
            ListNode* newnode=new ListNode(val);
            newnode->next=vir_node->next;
            vir_node->next=newnode;
            size++;
        }
        void addAttail(int val)
        {
            ListNode* new_node=new ListNode(val);
            ListNode* cur=vir_node;
            while (cur->next!=nullptr)
            {
                cur=cur->next;
            }
            cur->next=new_node;
            size++;
        }
        void addAtindex(int index,int val)
        {
            if(index>size)
            {
                return;
            }
            ListNode* new_node=new ListNode(val);
            ListNode* cur=vir_node;
            while (index--)
            {
                cur=cur->next;
            }
            new_node->next=cur->next;
            cur->next=new_node;
            size++;    
        }
        void deleteAtval(int val)
        {
            ListNode* cur=vir_node;
            while (cur->next!=NULL)
            {
                if(cur->next->val==val)
                {
                    ListNode* tmp=cur->next;
                    cur->next=cur->next->next;
                    delete tmp;
                    size--;
                }
                cur=cur->next;
            }
            
        }
        void deleteAtindex(int index)
        {
            if(index>=size|| index<0)
            return;
            ListNode*cur=vir_node;
            while (index--)
            {
                cur=cur->next;
            }
            ListNode*tmp =cur->next;
            cur->next=cur->next->next;
            delete tmp;
            size--;
        }
        void printLinklist()
        {
            ListNode* cur=vir_node;
            while (cur->next!=nullptr)
            {
                cout<<cur->next->val<<' ';
                cur=cur->next;
            }
            
        }
    //循环方式翻转链表
      void reverse_listnode()
        {
        ListNode* head=vir_node->next;
        ListNode* cur=head;
        ListNode*tmp;
        ListNode*pre=NULL;
        while (cur)
        {
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
            cout<<"翻转后: "<<endl;
            while(pre!=nullptr)
            {
                cout<<pre->val<<' ';
                pre=pre->next;
            }
    
        
    }
    //递归方式翻转链表
       /*ListNode* reverse_listnode_2(ListNode* pre,ListNode* cur){
            if(cur == NULL) return pre;
            ListNode* temp = cur->next;
            cur->next = pre;
    
            return reverse_listnode_2(cur,temp);
        }
    
        void reverseList(ListNode* head) 
        {
             reverse_listnode_2(NULL, head);
        }*/
        private:
        int size;
        ListNode* vir_node;
    };
    int main()
    {
       Mylink_list mylist;
       mylist.addAthead(1);
       mylist.addAttail(3);
       mylist.addAtindex(1,2);
       mylist.get(1);
       mylist.deleteAtindex(1);
       mylist.get(1);
       mylist.printLinklist();
       cout<<endl;
       mylist.reverse_listnode();
       cout<<endl;
       return 0;
    }

    结果:

    1 3
    翻转后:
    3 1

    展开全文
  • C++ 链表遍历

    2022-06-09 16:31:03
    C++ 链表遍历
  • c++ 链表的创建与链表常见操作

    千次阅读 2022-06-09 16:03:00
    C++链表的常见操作
  • C++链表通讯录系统

    2018-07-01 10:41:14
    C++链表通讯录系统,适合新手学习,可以实现添加,修改,删除,查询,文件保存文件打开功能,拿来学习还不错
  • 数据结构C++链表

    2018-03-04 20:04:54
    基于C++的数据结构单链表,带主程序可运行,使用头文件可直接编程。
  • c++链表(详解版)

    万次阅读 多人点赞 2019-06-13 16:27:57
    在自学C++的时候,看到好多人都在提链表,于是就自学了一下,看了很多别人的文章,加入了一些自己的理解,做了一下总结
  • c++链表学习——指针

    千次阅读 2022-03-13 13:30:46
    #include <iostream> #include <cstring> using namespace std; struct link { int elem; struct link* next; }; // link* initLink();//初始化 link* insertElem(link* p, ...int selectElem(link* p,
  • c++链表基本操作

    千次阅读 2022-01-22 20:30:01
    linklist* creat(int n) {//创建含有n个节点的链表 linklist* head; linklist* node; linklist* end; head = new linklist;//申请表头空间 end = head; head->data = n; //可以选择从表头开始存放所需数据...
  • c++结构体链表的简单排序,删除,添加等介绍和学习。。。
  • 1.认识链表 什么是链表链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链接的入口...
  • C++链表详细教程

    千次阅读 2022-06-15 17:30:41
    链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入...
  • C++链表类模版link.h

    2020-05-09 22:57:56
    C++链表类模版 //构造函数 //创建n个元素的列表 //拷贝构造 //释放链表 //析构函数(虚) //输出链表 //用t替换掉当前结点内容 //重载赋值运算符= //获取当前链表的长度或结点数 // 当前结点位置:第 n (从 0 起)...
  • C++链表入门实例

    2021-11-13 09:31:26
    C++链表入门实例1. 使用结构体创建链表并加入新节点2.使用含构造函数的结构体创建链表 1. 使用结构体创建链表并加入新节点 #include <iostream> using namespace std; struct ListNode//定义链表的数据结构 {...
  • C++链表02:反转链表

    千次阅读 2022-03-23 15:18:45
    翻转链表。 题意:反转一个单链表。 示例: 输入: 2->3->4->5->NULL 输出: 5->4->3->2->NULL 2.迭代 如图, 定义pre指针,初始化为 nullptr; 定义cur指针,指向头结点; 定义temp指针,...
  • C++链表类 模板类

    2012-11-20 22:38:20
    C++链表类 模板类 #include #include #include "LinkedList.h" using namespace std; template Node<T> *LinkedList<T>::GetNode(const T& item, Node* ptrNext) //生成新结点 { Node<T> *p; p = new Node...
  • c++链表的创建,插入和删除简单的综合,适合初学者
  • c++实现链表增删改查

    2021-07-17 19:51:55
    c++实现链表增删改查
  • 简单的C++链表问题,欢迎大家下载
  • C++ 链表(list)使用简述

    千次阅读 2022-03-28 11:29:08
    C++ STL 库的 list 容器是一个双向链表。包含在头文件 <list> 中 1、有关函数的作用 list 本身: list<type> li; 定义一个参数类型为 type 的链表 li.push_back(val) 在尾节点后插入...
  • C++链表的创建以及增删改查

    千次阅读 2021-12-18 20:15:48
    List.h文件 #pragma once #include<iostream> using namespace std; struct Node { int val; Node *pNext; Node(int val) { this->val = val; pNext = NULL; } ...//创建链表 vo.
  • C++链表类模板

    千次阅读 2020-01-28 12:12:41
    C++链表类模板 链表(list),即双向链表容器,它不支持随机访问,访问链表元素要指针从链表的某个断点开始,插入和删除操作所花费的时间是固定的,和该元素在链表中的位置无关。list在任何位置插入和删除动作都很快...
  • c++链表实现集合交集并集差集运算

    千次阅读 2022-03-27 20:40:02
    //创建链表 struct Node { int content; Node* next; }; //输入集合 Node* input_set() { Node* head = NULL, *tail=NULL; int x; cin >> x; while (x != 10086) { Node*p = new Node; ...
  • c++链表排序

    千次阅读 2021-03-17 10:45:18
    } //链表冒泡排序 void bubbleSort(stulist &head) { stulist p,pre, tail; tail = NULL; while(head -> next != tail) { pre = head; p = head -> next; while(p -> next != tail) { cout<Major<<" "<next->Major,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 176,713
精华内容 70,685
关键字:

c++链表

友情链接: cs.rar