链表反转

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

反转API：

public void reverse（）：对整个链表反转

public Node reverse（Node curr）：反转链表中的某个结点 curr ，并把反转后的 curr 结点返回

原链表：

递归反转：

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

链表实现

public class Inverted_LinkedList<T> implements Iterable<T> {
    //头结点
    private Node head;
    //元素总个数
    private int n;
    //单链表
    public class Node {
        //存储元素
        public T item;
        //指向下一个结点
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    //初始化
    public Inverted_LinkedList() {
        //初始化头节点
        this.head = new Node(null, null);
        //初始化个数
        this.n = 0;
    }
    //插入
    public void insert(T t) {
        //找到当前最后一个结点
        Node m = head;
        while (m.next != null) {
            m = m.next;
        }
        //创建新结点，值为t
        Node nNode = new Node(t, null);
        //最后一个结点指向新结点
        m.next = nNode;
        //元素个数+1
        n++;
    }
    //实现循环遍历
    @Override
    public Iterator<T> iterator() {
        return new Literator();
    }
    public 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() {
    //链表是否为空
    if (n==0){
        return;
    }
    //从第一结点开始
    reverse(head.next);
}
//反转指定的结点curr，并把 反转后的结点 返回
public Node reverse(Node curr) {
    //如果传入结点为最后一个结点，让头结点直接指向它
    if (curr.next==null){
        head.next=curr;
        return curr;
    }
    //递归反转当前结点
    Node pre = reverse(curr.next);
    //反转后的结点指向当前结点，进行反转
    pre.next=curr;
    //当前结点指向null
    curr.next=null;
    //返回当前结点
    return curr;
}

代码测试

public static void main(String[] args) {
    //创建单向链表对象
    Inverted_LinkedList<String> sl = new Inverted_LinkedList<>();
    //测试插入
    sl.insert("T1");
    sl.insert("T2");
    sl.insert("T3");
    for (String s : sl) {
        System.out.println(s);
    }
    System.out.println("-------------------------");
    sl.reverse();
    for (String s : sl) {
        System.out.println(s);
    }
}