《剑指Offer》反转链表

题目描述：

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

解题思路：

  本题比较简单，有两种方法可以实现：（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;   
    }