单向链表的反转--（JAVA语言实现，递归）

单向链表的反转

反转API：
public void reverse():对整个链表反转；
public Node reverse(Node curr):反转链表中的某个结点curr,并把反转后的curr结点返回；
使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点，知道把最后一个结点反转完成，整个链表就反转完毕。代码如下：

public class linkRevarse(){
	....................
	...............
	.........
	.......
	....//上面省略了一些代码，想要看完整的代码，在下面的代码块中
	//用来反转整个链表
    public void reverse(){
        //判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
        if(isEmpty()){
            return;
        }
        reverse(head.next);
    }

    //反转指定的结点curr,并把反转后的结点返回
    public Node reverse(Node curr){
        if(curr.next == null){
            head.next = curr;
            return curr;
        }
        //递归的反转当前结点curr的下一个结点，返回值就是链表反转后，当前结点的上一个结点
        Node pre = reverse(curr.next);

        //让返回的结点的下一个结点变为当前结点curr
        pre.next = curr;

        //把当前结点的下一个结点变为null
        curr.next = null;

        return curr;
    }
}

完整的代码块，在双向链表中添加反转

import cn.itcast.demo.day02.linear.SequenceList;

import java.util.Iterator;

public class LinkList<T> implements Iterable<T> {
    //记录头结点
    private Node head;
    //记录链表的长度
    private int N;

    //节点类
    private class Node{
        //存储数据
        T item;
        //下一个节点
        Node next;

        //内部类的构造函数
        public  Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }

    //LinkList的构造函数
    public LinkList(){
        //初始化头结点
        this.head = new Node(null,null);
        //初始化元素个数
        this.N = 0;
    }

    //清空链表
    public void clear(){
        head.next = null;
        this.N = 0;
    }

    //获取链表的长度
    public int length(){
        return N;
    }

    //判断链表是否为空
    public boolean isEmpty(){
        return N==0;
    }

    //获取指定位置i处的元素(非物理位置，0,1,2,3,......)
    public T get(int i){
            //通过循环，从头节点开始往后找，依次找i次就可以找到对应的元素
            /*
                注：head0.item = null;
                0,1,2,3,4,5.....,
                index == 0时：取得时head1.item;
                index == 1时：取得时head2.item;
                index == 2时：取得时head3.item;
                ......................
                index == i-1时：取得时headi.item;
             */
            Node n = head.next;
            for(int index = 0; index < i; index++){
                n = n.next;
            }
            return n.item;

    }
    //向链表中添加元素t(非物理位置，0,1,2,3,......)
    public void insert(T t){
        //找到当前最后一个节点
        Node n = head;
        while (n.next != null){
            n = n.next;
        }
        //创建新节点，保存元素t
        Node newNode = new Node(t,null);
        //让当前最后一个节点指向新节点
        n.next = newNode;
        //元素个数+1
        N++;
    }

    //向指定位置i处，添加元素t(物理位置，1,2,3,......)
    public void insert(int i,T t){
        //找到i位置前一个节点
        Node pre = head;
        for(int index = 0; index < i-1; index++){
            pre = pre.next;
        }

        //找到i位置的节点
        Node curr = pre.next;
        //创建新节点，并且新节点需要指向原来i位置的节点
        Node newNode = new Node(t,curr);
        //原来i位置的前一个节点指向新节点
        pre.next = newNode;
        //元素个数+1；
        N++;
    }

    //删除指定位置i处的元素，并返回被删除的元素
    public T remove(int i){//(非物理位置，0,1,2,3,......)
        //找到i位置的前一个节点
        Node pre = head;
        for(int index = 0; index < i-1; index++){//??????????
            pre = pre.next;
        }
        //要找到i位置的节点
        Node curr = pre.next;
        //找到i位置的下一个节点
        Node nextNode = curr.next;
        //前一个节点指向下一个节点
        pre.next = nextNode;
        //元素个数-1
        return curr.item;
    }

    //查找元素t在链表中第一次出现的位置
    public int indexOf(T t){
        //从头节点开始，依次找到每一个结点，取出item和t进行比较如果相同就找到了
        Node n = head;
        for(int i = 1; n.next!=null; i++){
            n = n.next;
            if(n.item.equals(t)){
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n = head;
        }

        @Override
        public boolean hasNext(){
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }

    }

    //用来反转整个链表
    public void reverse(){
        //判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
        if(isEmpty()){
            return;
        }
        reverse(head.next);
    }

    //反转指定的结点curr,并把反转后的结点返回
    public Node reverse(Node curr){
        if(curr.next == null){
            head.next = curr;
            return curr;
        }
        //递归的反转当前结点curr的下一个结点，返回值就是链表反转后，当前结点的上一个结点
        Node pre = reverse(curr.next);

        //让返回的结点的下一个结点变为当前结点curr
        pre.next = curr;

        //把当前结点的下一个结点变为null
        curr.next = null;

        return curr;
    }
}