Leetcode 206 Question Reverse Linked List (Reverse Linked List) Java language solution

Leetcode 206 Question Reverse Linked List (Reverse Linked List) Java language solution

Title description:

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Iterative solution

/**
Definition for singly-linked list.
public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
}
 */

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

Explain the code:
1. Prepare two empty sections pre and next for subsequent operations, where pre saves the node before head, and next makes temporary changes.
2. If the head is not empty, enter the loop body and turn to 3; otherwise, exit the loop , Return to pre, the program ends.
3. 1. assign the temporary variable next to the next value of head, so that the linked list will continue during the operation, turn 4;
4. Assign pre (the previous element of head) to the next of head, turn 5;
5. Change Pre is assigned to the value of the current head, turn to 6.
6. Move the head back one bit, and assign the current value of next, to 2.

Screenshot of submission result:

submit

Recursive solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode reverseList(ListNode head) {
       //1.
        if(head == null || head.next == null){
           return head;
       }
       //2.
        ListNode reve = reverseList(head.next);
        //3.
        head.next.next = head;
        head.next = null;
        return reve;
    }
}

Explain the code:
1. First look at the recursive header, which is the basic problem of the problem: if the input is empty or there is only one node, it can be returned directly without inversion;
2. Divide the big problem into small problems: it is the inversion A linked list consisting of head.next and the following nodes is enough;
3. Turn the solution of the small problem into the solution of the big problem: point the next of the original head.next to the head, and the next of the original head can be empty. Screenshot of submission result:

The above is the iterative and recursive solutions of the inverted linked list.

Welcome to follow

Scan the QR code below to follow: