Linked list (III) - reverse linked list

Here's the head node of the list head, Please reverse the list , And return the inverted linked list

Power button 206 Reverse a linked list

Example ：

Input ：head = [1,2,3,4,5]
Output ：[5,4,3,2,1]

Tips ：

• The number range of nodes in the linked list is [0, 5000]
• -5000 <= Node.val <= 5000

Double pointer

Observe the structure of the single linked list , Just reverse the pointer of the linked list

• Change the pointer from the position of the node
• pre Point to null,cur Point to the head node
• take cur Change the direction of pre
• use temp Store cur Point to the next node , For the next reversal
• curpre Move the pointing back one position , until cur Point to null
  

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
    
            temp = cur.next;//  Save the next node 
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

recursive

The operation is repeated in a double pointer , You can also use recursion

• Determine the boundary conditions

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        //  Initialization conditions 
        return reverse(null, head);
    }
    public ListNode reverse(ListNode pre, ListNode cur) {
    
       //  Jump out of recursive conditions 
        if (cur == null) {
    
            return pre;
        }
        ListNode temp = null;
        temp = cur.next;//  Save the next node first 
        cur.next = pre;//  reverse 
        return reverse(cur, temp); //  Update location 
    }
}