17. Reverse the linked list

Given the head node of a single linked list pHead( The header node has a value , For example, in the figure below , its val yes 1), The length is n, After reversing the linked list , Return the header of the new linked list .

Data range ： 0\leq n\leq10000≤n≤1000
requirement ： Spatial complexity  O(1)O(1) , Time complexity  O(n)O(n) .
For example, when entering a linked list {1,2,3} when ,
After reversal , The original linked list becomes {3,2,1}, So the corresponding output is {3,2,1}.

Example 1
Input ：
{1,2,3}
Copy the return value ：
{3,2,1}
Copy

Example 2
Input ：
{}
Copy the return value ：
{}
Copy instructions ：
Empty linked list will output empty          

The code is as follows ：

import lombok.ToString;

@ToString
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode head = new ListNode(1);
        ListNode headOne = new ListNode(2);
        ListNode headTwo = new ListNode(3);
        head.next = headOne;
        headOne.next = headTwo;
        System.out.println(head);
        System.out.println(reverseList(head));
    }

    public static ListNode reverseList(ListNode head) {
        // pre The pointer ： Used to point to the inverted node , Initialize to null
        ListNode pre = null;

        //  Current node pointer 
        ListNode cur = head;

        //  Loop iteration 
        while (cur != null) {
            // curNext  node , Always point to the current node cur The next node of 
            ListNode curNext = cur.next;

            //  The key to reversal ： The current node points to its previous node ( Note that this is not a two-way linked list , No precursor pointer )
            cur.next = pre;

            //  to update pre
            pre = cur;

            //  Update the current node pointer 
            cur = curNext;
        }

        //  Why return to pre？ because pre Is the head node after inversion 
        return pre;
    }
}