（链表反转）单向链表反转是⼀道经典算法问题，⽐如有⼀个链表是这样的 $1 -> 2 -> 3 -> 4 -> 5$，反转后成为 $5 -> 4 -> 3 -> 2 -> 1$ 。现给定如下链表节点的定义：
struct linkNode {
int value;
linkNode* next;
};
⾮递归实现：
linkNode* Reverse(linkNode* header) {
if (header == NULL || header->next == NULL) {
return header;
}
linkNode *pre = header, *cur = header->next;
pre->next = NULL;
while (cur != NULL) {
linkNode* next = ___(1)___;
___(2)___ = pre;
pre = cur;
cur = next;
}
return pre;
}
递归实现：
linkNode* Reverse(linkNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
linkNode* newhead = ___(3)___;
___(4)___ = head;
head->next = ___(5)___;
return newhead;
}
1. B。
2. B。
3. D。
4. C。
5. D。
通过两段代码不同的⽅式实现了列表的翻转，核⼼思想就是每次处理列表中两个相邻的节点，通过交换指针的⽅式来重新组织其顺序。第⼀段代码就是通过迭代的⽅式来进⾏访问的，记录下来相邻的节点，并交换其指针。第⼆段代码是通过递归的⽅式来访问的，函数返回值是翻转后的链表头指针，每层递归都是翻转两个相邻的节点。