《算法之美》の链表问题の单向链表的反转

题目：输入一个链表的头节点，反转这个链表，并返回反转后链表的头节点，链表定义如下：

struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};

解答：

算法一：我们需要额外的两个变量来存储当前节点pCurrent的上一个节点pPrev和下一个节点pNext。假设经过若干次操作，我们将当前节点pCurrent之前的指针都反转完成，这些节点的m_pNext指针都指向前面的一个节点。现在我们遍历到pCurrent，这时需要调整该节点的m_pNext指针使其指向pPrev节点。但要注意调整了m_pNext指针的指向后，后面的链表就会断开，因此我们需要在调整pCurrent的m_pNext指针之前先将pNext节点保存下来。反转后的头节点就是原来的尾节点。

核心代码如下：

//反转链表核心算法

ListNode* ReverseList(ListNode* pHead)

{

ListNode* pReverseHead = NULL;

ListNode* pNode = pHead->m_pNext;

ListNode* pPrev = NULL;

while(pNode != NULL)

{

//存储当前节点pNode的下一个节点

ListNode* pNext = pNode->m_pNext;

//如果下一个节点为空，那么当前节点pNode就是反转后的头指针了

if(pNext == NULL)

{

pReverseHead = pNode;

}

//将当前节点改为指向pPrev节点

pNode->m_pNext = pPrev;

//移动两个指针

pPrev = pNode;

pNode = pNext;

}

//添加头指针

ListNode* pReturn = (ListNode*)malloc(sizeof(ListNode));

pReturn->m_pNext = pReverseHead;

return pReturn;

}

算法二：递归法，基本思想是在反转当前节点之前先调用递归函数反转后续节点，该方法在反转后的最后一个节点会形成一个环，所以必须将函数的返回节点的m_pNext域置为NULL。

ListNode* ReverseLink(ListNode* pHead)

{

if(pHead->m_pNext == NULL)

return pHead;

ListNode* pReturn = ReverseLink(pHead->m_pNext);

pHead->m_pNext->m_pNext = pHead;

pHead->m_pNext = NULL;

return pReturn;

}

//反转链表的递归算法

ListNode* ReverseList2(ListNode* pHead)

{

ListNode* pReverseHead = pHead;

//考虑只有0个或1个节点

if(pHead->m_pNext == NULL || pHead->m_pNext->m_pNext == NULL)

{

return pHead;

}

pReverseHead->m_pNext = ReverseLink(pReverseHead->m_pNext);

return pReverseHead;

}

完整测试代码如下：

#include <iostream>

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

void InitList(ListNode** head)

{

*head = (ListNode*)malloc(sizeof(ListNode));

(*head)->m_pNext = NULL;

}

void InsertList(ListNode* head, int data)

{

assert(head != NULL);

ListNode* pNewNode = (ListNode*)malloc(sizeof(ListNode));

pNewNode->m_nKey = data;

pNewNode->m_pNext = head->m_pNext;

head->m_pNext = pNewNode;

}

void PrintList(ListNode* pHead)

{

if(pHead == NULL)

{

return;

}

ListNode* pTempNode = pHead->m_pNext;

while(pTempNode != NULL)

{

std::cout<<pTempNode->m_nKey<<std::endl;

pTempNode = pTempNode->m_pNext;

}

}

//反转链表核心算法

ListNode* ReverseList(ListNode* pHead)

{

ListNode* pReverseHead = NULL;

ListNode* pNode = pHead->m_pNext;

ListNode* pPrev = NULL;

while(pNode != NULL)

{

//存储当前节点pNode的下一个节点

ListNode* pNext = pNode->m_pNext;

//如果下一个节点为空，那么当前节点pNode就是反转后的头指针了

if(pNext == NULL)

{

pReverseHead = pNode;

}

//将当前节点改为指向pPrev节点

pNode->m_pNext = pPrev;

//移动两个指针

pPrev = pNode;

pNode = pNext;

}

//添加头指针

ListNode* pReturn = (ListNode*)malloc(sizeof(ListNode));

pReturn->m_pNext = pReverseHead;

return pReturn;

}

ListNode* ReverseLink(ListNode* pHead)

{

if(pHead->m_pNext == NULL)

return pHead;

ListNode* pReturn = ReverseLink(pHead->m_pNext);

pHead->m_pNext->m_pNext = pHead;

pHead->m_pNext = NULL;

return pReturn;

}

//反转链表的递归算法

ListNode* ReverseList2(ListNode* pHead)

{

ListNode* pReverseHead = pHead;

//考虑只有0个或1个节点

if(pHead->m_pNext == NULL || pHead->m_pNext->m_pNext == NULL)

{

return pHead;

}

pReverseHead->m_pNext = ReverseLink(pReverseHead->m_pNext);

return pReverseHead;

}

int main()

{

ListNode* pListHead = NULL;

InitList(&pListHead);

//建立两个链表

for(int i=9; i>=0; i--)

{

InsertList(pListHead, i);

}

std::cout<<"链表反转之前："<<std::endl;

PrintList(pListHead);

//ListNode* pReverseHead = ReverseList(pListHead);

ListNode* pReverseHead = ReverseList2(pListHead);

std::cout<<"链表反转之后："<<std::endl;

PrintList(pReverseHead);

system("pause");

return 0;

}