C++笔试题汇总：链表反转等经典问题解析

"c++笔试题汇总，包含了链表反转等常见面试题目，提供了两种链表反转的实现方式：一种是迭代法，另一种是递归法。同时提到了String类的通用构造函数。" 在C++的笔试题中，链表反转是一个经典的问题，主要考察程序员对数据结构和算法的理解。链表反转有多种方法，这里提到了两种常见的方法：迭代法和递归法。 1. 迭代法： 这种方法通过遍历链表，利用一个辅助指针存储当前节点的下一个节点，然后反转当前节点的next指针指向它的前一个节点。在遍历过程中，pre指针始终保存前一个节点，cur指针指向当前节点，ne指针用于临时存储下一个节点。当遍历结束后，head指针会被更新为反转后的链表头。以下是对这种方法的代码实现： ```cpp struct Linka { int data; Linka* next; }; void reverse(Linka*& head) { if (head == NULL) return; Linka* pre, * cur, * ne; pre = head; cur = head->next; while (cur) { ne = cur->next; cur->next = pre; pre = cur; cur = ne; } head->next = NULL; // 防止形成环，设置头节点的next为NULL head = pre; // 更新head指针为反转后的头节点 } ``` 2. 递归法： 递归法则是通过递归调用来实现链表反转，首先反转后续节点，然后再处理当前节点。递归函数接受两个参数，一个是当前节点p，另一个是head指针的引用。当递归到链表末尾时，返回头节点。在处理非末尾节点时，递归反转后续节点，然后将当前节点插入到反转后的链表前面。以下是递归法的代码实现： ```cpp Linka* reverse(Linka* p, Linka*& head) { if (p == NULL || p->next == NULL) { head = p; return p; } else { Linka* tmp = reverse(p->next, head); tmp->next = p; return p; } } ``` 递归法需要注意的是，反转结束时需要将返回节点的next指针设为NULL，以断开反转形成的环。 此外，题目中还提到了String类的通用构造函数。在C++中，String类通常用于处理字符串，其通用构造函数可能如下所示： ```cpp class String { public: String(const char* str = NULL); // 通用构造函数，可以接受空字符串或者字符数组 // ...其他成员函数和数据成员... }; ``` 这个构造函数允许创建一个String对象，可以不传入参数创建一个空字符串，也可以传入一个const char*类型的字符串（如C风格的字符串）来初始化String对象。