关于后端: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;
    }
}