网站返回按钮设计/我要下载百度

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不再有用。