搜狐2013届校园招聘笔试题目是：分别用迭代和递归的方法对单链表进行逆转。听今天去华为参加机试的同学说，三道机试题目中也有一道同样的题目。由是自己动手写了写，代码如下：

        typedef struct LinkNode

        {

                 ElementType  data;

                 struct LinkNode *next;

         } node;

  代码1：迭代方法

node* rLink(node *head)

{

      if(head == NULL || head->next == NULL)

           return head;

      node *p1 = head;

      node *p2 = p1->next;

      node *p3 = p2->next;

      p1->next = NULL;

 

      while(p3 != NULL)

      {

           p2->next = p1;

           p1 = p2;

           p2 = p3;

           p3 = p3->next;

       }

       p2->next = p1;

       head = p2;

       return head;

}

代码2：递归方法

         

        p1 和p2指针分别指向当前递归子链表list1的第一个和第二结点。然后对以p2为首结点的子链表list2进行递归逆转；则p2节点将成为list2r逆转后的尾结点，而此时函数返回的头结点将是原list2的尾结点（如下图）。最后我们只要把p2的next指向p1就OK了。

                                               

 

        node* recursive_Link(node* head)

        {

              if(head == NULL || head->next == NULL)

                    return head;

              node* p1 = head;

              node* p2 = p1->next;  //p2其实记录的下一步递归过程后的尾结点

              head = recursive_Link(p2);

              p2->next = p1;

              p1->next = NULL;

               return head;

         }