面试题16:反转链表

发布于:2021-10-25 11:33:11

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

?假设有链表A->B->C->D->E->F->G。在反转链表过程中的某一阶段,其链表指针指向为:A<-B<-C<-D ?E->F->G。也就是说在结点D之前的所有结点都已经反转,而结点D后面的结点E开始的所有结点都没有反转。这样D跟E之间存在了断裂。我们如果要实现链表的反转,会有以下几个重要步骤:


    D->E变为D->C,指针反转指针往后移动一个,操作下一个结点E结合1.2我们发现需要操作3个指针,分别是C,D,E。

因此可以考虑存储C/D/E三个结点的指针,通过这三个结点的指针实现反转。


代码实例:





View Code

#include
#include
#include
using namespace std;

//链表结构
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};

//创建一个链表结点
ListNode* CreateListNode(int value)
{
ListNode *pNode=new ListNode();
pNode->m_nValue=value;
pNode->m_pNext=NULL;
return pNode;

}

//遍历链表中的所有结点
void PrintList(ListNode* pHead)
{
ListNode *pNode=pHead;
while(pNode!=NULL)
{
cout<m_nValue<<" ";
pNode=pNode->m_pNext;
}
cout<}

//往链表末尾添加结点
/*
注意这里pHead是一个指向指针的指针,在主函数中一般传递的是引用。
因为如果要为链表添加结点,那么就会修改链表结构,所以必须传递引用才能够保存修改后的结构。
*/
void AddToTail(ListNode** pHead,int value)
{
ListNode* pNew=new ListNode();//新插入的结点
pNew->m_nValue=value;
pNew->m_pNext=NULL;

if(*pHead==NULL)//空链表
{
*pHead=pNew;
}
else
{
ListNode* pNode=*pHead;
while(pNode->m_pNext!=NULL)
pNode=pNode->m_pNext;
pNode->m_pNext=pNew;
}

}

ListNode* ReverseList(ListNode* pHead)
{
ListNode* pNode=pHead;//当前结点
ListNode* pPrev=NULL;//当前结点的前一个结点
ListNode* pReversedHead=NULL;//反转链表头结点
while(pNode!=NULL)
{
ListNode* pNext=pNode->m_pNext;
if(pNext==NULL)//如果当前结点的下一个结点为空,那么反转链表的头结点就是当前结点。
pReversedHead=pNode;

pNode->m_pNext=pPrev;//当前结点指向前一个结点

pPrev=pNode;//pPrev和pNode往前移动。
pNode=pNext;//这里要使用前面保存下来的pNext,不能使用pNode->m_pNext
}
return pReversedHead;//返回反转链表头指针。
}

void main()
{
//创建结点
ListNode* pNode1=CreateListNode(1);//创建一个结点
PrintList(pNode1);//打印
//往链表中添加新结点
AddToTail(&pNode1,2);//为链表添加一个结点
AddToTail(&pNode1,3);//为链表添加一个结点
AddToTail(&pNode1,4);//为链表添加一个结点
AddToTail(&pNode1,5);//为链表添加一个结点
AddToTail(&pNode1,6);//为链表添加一个结点
AddToTail(&pNode1,7);//为链表添加一个结点
//打印链表
PrintList(pNode1);//打印
//反转链表
ListNode* pReversedHead=ReverseList(pNode1);
PrintList(pReversedHead);//打印

system("pause");

}


运行结果:


1

ps:2012-5-3

发现有一种更加简洁的写法,就是不需要pReversedHead指针,从上述程序我们可以看出来pReversedHead指针只是单纯的用来保存反转链表的头指针,但是pPrev和pNode指针其实就包含反转链表的头指针,因此我们没有必要单独定义一个头指针来保存。修改后的函数如下所示:





View Code

ListNode* ReverseList2(ListNode* pHead)
{
ListNode* pNode=pHead;//当前结点
ListNode* pPrev=NULL;//当前结点的前一个结点
while(pNode!=NULL)
{
ListNode* pNext=pNode->m_pNext;
pNode->m_pNext=pPrev;//当前结点指向前一个结点

pPrev=pNode;//pPrev和pNode往前移动。
pNode=pNext;//这里要使用前面保存下来的pNext,不能使用pNode->m_pNext
}
return pPrev;//返回反转链表头指针。
}


?


?

相关推荐

最新更新

猜你喜欢