应用介绍

此项目是c++笔试题汇总。

展示附件中一小部分：

单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比

如一个链表是这样的： 1->2->3->4->5 通过反转后成为 5->4->3->2->1。

最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针

指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往

后面继续遍历。源代码如下：

1. struct linka {

2. int data;

3. linka* next;

4. };

5. void reverse(linka*& head) {

6. if(head ==NULL)

7. return;

8. linka *pre, *cur, *ne;

9. pre=head;

10.cur=head->next;

11.while(cur)

12.{

13. ne = cur->next;

14. cur->next = pre;

15. pre = cur;

16. cur = ne;

17.}

18.head->next = NULL;

19.head = pre;

20.}

还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递

归函数反转后续节点。源代 码如下。不过这个方法有一个缺点，就是在反转后

的最后一个结点会形成一个环，所以必须将函数的返回的节点的 next 域置为

NULL。因为要改变 head 指 针，所以我用了引用。算法的源代码如下：

1. linka* reverse(linka* p,linka*& head)

2. {

3. if(p == NULL || p->next == NULL)

4. {

5. head=p;

6. return p;

7. }

8. else

9. { 10. linka* tmp = reverse(p->next,head);

11. tmp->next = p;

12. return p;

13.}

14.}