《剑指offer》反转链表-ag真人游戏

题目描述：

  输入一个链表，反转链表后，输出新链表的表头。

解题思路：

  本题比较简单，有两种方法可以实现：（1）三指针。使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。将指针反转后，三个结点依次前移即可。（2）递归方法。同样可以采用递归来实现反转。将头结点之后的链表反转后，再将头结点接到尾部即可。

代码实现(c )

/**
*  struct listnode {
*        int val;
*        struct listnode *next;
*        listnode(int x) :
*              val(x), next(null) {
*        }
*  };
*/
class solution
{
public:
    listnode* reverselist(listnode* phead)
    {
        listnode *preversedhead = null;
        listnode *pnode = phead;
        listnode *pprev = null;
        listnode *pnext = null;
        // pprev -> pnode -> pnext;
        while(pnode != null)
        {
            pnext = pnode->next;        //  保存其下一个节点
            pnode->next = pprev;        //  指针指向反转
            pprev = pnode;              //  保存前一个指针
            pnode = pnext;              //  递增指针, 指向下一个结点
        }
        return pprev;           //  最后pprev指针指向的那个节点就是原来的未指针，新的头指针
    }
};

代码实现(java)

 //方法一：三指针
    public listnode reverselist(listnode head) {
        if(head==null)
            return null;
        listnode first=null; 
        listnode second=head;
        listnode third=head.next;
        while(third!=null){ 
            second.next=first; //三指针之间的变换
            first=second;
            second=third;
            third=third.next;
        }
        second.next=first;
        return second;
    }
    //方法二：递归
    public listnode reverselist(listnode head) {
         if(head==null||head.next==null)
            return head;
        listnode temp=reverselist(head.next);
        head.next.next=head;
        head.next=null;
        return temp;   
    }