反转链表
博客专区 > htq 的博客 > 博客详情
反转链表
htq 发表于1年前
反转链表
  • 发表于 1年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

要求:定义一个函数,将一个链表反转。链表节点定义如下:

struct ListNode
{
	int data;
	ListNode *m_pNext;
};
思路:所谓反转即将链表中某个节点的原本指向后一个节点的指针域指向前一个节点,如果用pCurrent表示当前处理节点,pPrev表示当前处理节点的前一个节点,则很容易想到,反转即pCurretn->m_pNext=pPrev;但是如果直接这么操作的话,因为当前处理节点的下一个节点(记为pNext)的地址保存在pCurrent->m_pNext中,所以如果直接将当前节点指向前一个节点,则pNext的地址丢失,所以不能直接将pCurretn->m_pNext=pPrev;在这个语句之前,我们应该保存pNext的值,即pNext=pCurrent->m_pNext;
用图表示思路如下:

基于上述思路代码如下:

void reverseList(ListNode * pHead)
{
	ListNode *pCurrent=pHead->m_pNext;//pCurrent的初始值指向第一个节点
	pHead->m_pNext=NULL;//首先断开头节点
	while(pCurrent!=NULL)
	{
		ListNode *pNext=pCurrent->m_pNext;//保存pNext的值,初始值指向第二个节点

		pCurrent->m_pNext=pHead->m_pNext;//每次从原链表中摘下当前处理节点,让其指向反转后链表的第一个节点,初始值为让原链表中的第一个节点的指针域置空
		pHead->m_pNext=pCurrent;//让头节点指向当前结点

		pCurrent=pNext;//将当前节点后移,指向下一个带插入的节点

	}
}


共有 人打赏支持
htq
粉丝 17
博文 67
码字总数 1007
作品 3
×
htq
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: