笔试题单向链表

笔试题（单向链表）

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

1->2->3->4->5
通过反转后成为5->4->3->2->1。
最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然

后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
    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;
    head = pre;
    }
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。

源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的

返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：
    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;
    }
    }
 

【笔试题单向链表】相关文章：

中兴2015笔试题08-02

迅雷2011.10.21笔试题08-10

海尔04年笔试题及答案07-31

交通银行2014笔试题题目分享08-10

阿里巴巴非技术类笔经及试题08-13

攀枝花移动笔试题，笔经分享08-10

QMS2007笔试审核知识模拟试题08-30

柜员合同工招聘笔试题型，笔经分享08-10

交通银行内蒙古分行2012笔试题，给2013的还只们08-09

腾讯笔试题 试题分享08-09