题解 | #反转链表#

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {

//         return reverseNodeMethod1(head);
        return reverseNodeMethod2(head);

    }

    public ListNode reverseNodeMethod1(ListNode head){

        if (head == null || head.next == null) {
            return head;
        }

        ListNode preNode = head;
        ListNode curNode = head.next;
        ListNode temp = null;

        while (curNode != null) {
            //1->2->3 先记住当前节点2的第三个节点3 采取的移动方法是先让2->1 然后再让3->2 一个一个倒挂到头节点 最后就变成了3->2->1
            temp = curNode.next;
            //头结点指向第三个节点 此时相当于操作head.next 即2节点 curNode只是个临时变量
            curNode.next = preNode;
            //让头节点此时从1变为2 此时2->1 temp记录了3 后续才能让3->2 这样就实现反转了
            preNode = curNode;
            //让当前操作节点变为3 此时让临时变量curNode指向3节点
            curNode = temp;
        }

        head.next = null;
        return preNode;
    }

    public ListNode reverseNodeMethod2(ListNode head){

        if (head == null || head.next == null) {
            return head;
        }

        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            len ++;
            temp = temp.next;
        }

        ListNode headNode = new ListNode(-1);
        headNode.next = head;

        ListNode curNode = head;
        ListNode tempNode = null;

        //从第二个节点开始进行头插
        for (int i = 1; i < len; i++) {
            tempNode = curNode.next;
            curNode.next = tempNode.next;
            tempNode.next = headNode.next;
            headNode.next = tempNode;
        }

        return headNode.next;
    }
}