单链表反转

public class SingleLinkedList {
    private class Node {
        private Node next;
        private int value;
        Node(Node next, int value) {
            this.next = next;
            this.value = value;
        }
    }
    
    private Node head;
    private Node last;
    private int size;
    
    public SingleLinkedList() {
        Node firstNode = new Node(null, 0);
        head = firstNode;
        last = firstNode;
        size = 0;
    }

    public void add(int value) {
        Node node = new Node(null, value);
        last.next = node;
        last = node;
        size++;
    }

    public void clear() {
        size = 0;
        last = head;
    }
    //将链表倒进数组，再从数组逆序拿出，耗费更多内存。
    public void reverse() {
        int oldSize = size;
        Node cursor = head.next;
        Node[] nodes = new Node[oldSize];
        for (int i = 0; i < oldSize; i++) {//save all value to the nodes
            nodes[i] = cursor;
            cursor = cursor.next;
        }
        clear();//clear the linkedList
        for (int i = oldSize - 1; i >= 0; i--) {
            add(nodes[i].value);
        }
    }
    private void print(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            print(node.next);
        }
    }
    public void print() {
        print(head.next);
    }
    //在原址上操作，通过递归从尾结点开始，将结点指针反转。
    private Node reverseHead(Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node newHead = reverseHead(node.next);
        node.next.next = node;
        node.next = null;
        return newHead;
    }
    public void reverseHead() {
        last = head.next;
        head.next = reverseHead(head.next);
    }
}

reverseHead方法的图解：

image.png

剩下的画图跟着代码走一遍。