关于后端:JAVA实现单链表头插法原地逆置

/**
 * 两种形式（递归和非递归）实现单链表原地逆置
 * leetcode #206
 */
public class Reverse {
    class Node{
        int value;
        Node next;
        Node(int x){value = x;}
    }
    // 非递归，双指针，头插法
    public Node reverse1(Node head){if(head == null || head.next == null){return head;}

        // p 存储第一个元素，r 用于 p 与前面链表断开时长期存储前面元素
        Node p = head.next, r;
        // 头节点断开
        head.next = null;
        while (p != null) {
            // r 长期存储后边的元素，因为 p 要与后边的断开
            r = p.next;
            // p 与前面断开，且指向头节点后边的元素
            p.next = head.next;
            // 头节点与 p 相连，p 插入到头节点与先来的元素之间
            head.next = p;
            // 后移一个，持续逆置
            p = r;
        }
        return head;
    }

    public Node reverse2(Node head){if(head == null || head.next == null){return head;}
        
        // 递归到链表开端，走下面的递归进口最初一个元素间接通过 return head 失去
        // 而后返回到倒数第二层执行最初三行代码，顺次失去逆置的元素
        // 能够依据下图帮忙了解
        Node newHead = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}