学步园

题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下：struct ListNode<br /> {<br /> int m_nKey;<br /> ListNode* m_pNext;<br /> };
解法一：起始节点为p1，令p2 = p1->next, p1->next = NULL。若p2为NULL，则返回p1；若p2不为NULL，进行如下循环：令p3 = p2->next。p2->next = p1;然后再令p1 = p2; p2 = p3;直到p2为NULL，退出循环。返回此时的p1，即为反转后链表的第一个节点。代码如下：node* reverse(node* head)<br /> {<br /> assert(head != NULL);<br /> node *p1 = head, p2 = p1->next, p3;<br /> p1->next = NULL;<br /> while (p2 != NULL)<br /> {<br /> p3 = p2->next;<br /> p2->next = p1;</p> <p> p1 = p2;<br /> p2 = p3;<br /> }<br /> return p1;<br /> }
解法二：采用递归。思路和解法一一样，只不过是用递归的形式。// 在递归调用之前，要判断head是否为NULL。结束之后要把原head的next置为NULL<br /> node* reverse(node* p1, node* p2)<br /> {<br /> if (p2 != NULL)<br /> {<br /> node *p3 = p2->next;<br /> p2->next = p1;<br /> return reverse(p2, p3);<br /> }</p> <p> return p1;<br /> }