Talk is cheap, show your code!
struct Node
{
int data;
Node* m_pNext;
Node(int d):data(d){m_pNext = NULL;}
};
1. 从前遍历到尾,依次反转指针的指向,原来的头指针的下一结点设置为空,原来的尾结点变成头结点返回。
Node* Reverse(Node*& head)
{
if(head == NULL)
{
return head;
}
Node* pre = NULL;
Node* cur = head;
Node* nex;
while(cur)
{
nex = cur->m_pNext;
cur->m_pNext = pre;
pre = cur;
cur = nex;
}
return head = pre;
}
2. 设置一个新的空链表,然后每次从原来的链表中取出最前面的元素,插入到这个新的链表之中,直到最后一个元素。
Node* Reverse2(Node*& head)
{
if (head == NULL) return head;
Node* pList = NULL; // 新的空链表。
Node* cur = head;
while(cur)
{
Node* Tmp = cur->m_pNext;
cur->m_pNext = pList;
pList = cur;
cur = Tmp;
}
return head = pList;
}
3. 采用递归。
Node* Reverse3(Node* head)
{
if (head == NULL || head->m_pNext == NULL)
return head;
Node* p = Reverse3(head->m_pNext);
head->m_pNext->m_pNext = head;
head->m_pNext = NULL;
return p;
}
这种递归的方式,需要注意的是,执行完后head不再有用。