顺序表-链表-单向链表反转

单向链表反转

预防面试被问，做个笔记

需求：

原链表中的数据为：1->2->3->4

反转链表后的数据为：4->3->2->1

反转链表Api

1	public void reverse()//对整个链表进行反转

1	public Node reverse(Node curr)//反转链表的某个结点，并把反转后的结点返回

使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点，直到把最后一个结点反转完毕，整个链表就反转完毕。

调用reverser(Node curr)方法反转每一个结点，从元素1开始；
如果发现curr还有下一个结点，则递归调用reverser(curr.next)对下一个结点进行反转
最终递归的出口为元素4结点，因为它没有下一个结点，当到了出口处，让head指向元素4结点，共调用4次
递归开始返回

如果不理解过程：debug 跟着流程走一遍

代码：

/**
 * 反转某个结点
 * @param curr 需要反转的结点
 * @return 返回反转的结点
 */
public Node reverse(Node curr){
    //递归的出口
    if (curr.next == null){
        head.next = curr;
        return curr;
    }
    //反转结点的下一个结点如果不为空，递归调用反转下一个结点
    //如果是head,1,2,3,4 这里进入的为4结点，返回的为head,4
    Node prev = reverse(curr.next);
    //这里就是反转 head，4,3
    prev.next = curr;
    curr.next = null;
    return curr;
}