单链表的反转

方法一

从第二个节点开始，依次把节点变成头个节点。

java

//链表无辅助头节点
public void 反转(){

   if(_头指针 == null){
            return;
        }

    节点 _目标节点的前一个元素 = _头指针;//第一个节点不用动

    while ( _目标节点的前一个元素._下一个节点 != null){
        节点 _目标节点 = _目标节点的前一个元素._下一个节点;

        _目标节点的前一个元素._下一个节点 = _目标节点._下一个节点;
        _目标节点._下一个节点 = _头指针;
        _头指针 = _目标节点;
    }
}

方法二

递归法，修改自己的下一个节点为null，然后返回自己给前一个节点。

java

//链表无辅助头节点
public void 递归反转(){

    if (_头指针 == null){
        return;
    }
    递归反转(_头指针);
}

private 节点 递归反转(节点 _当前节点){

    //最后一个节点: 把头指针指向最后一个节点
    if(_当前节点._下一个节点 == null){
        _头指针 = _当前节点;
        return _当前节点;
    }

    //当前节点的下一个节点完成它该做的操作之后, 把自己反回去
    节点 _当前节点的下一个节点 = 递归反转(_当前节点._下一个节点);

    //因为要反转, 把返回来的下一个节点指向当前节点
    _当前节点的下一个节点._下一个节点 = _当前节点;

    //因为不知道那那一个节点是未反转前头一个节点, 所以假设每个节点都是
    // 如果不是, 当递归到它前一个元素时, 上面一行代码会将这个节点的下一节点修正
    _当前节点._下一个节点 = null;

     return _当前节点;
}