Title description:
Reverse a single linked list. Example: input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL
Iterative method
/ * *
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;
}
}
Copy the code1. Prepare two empty sections pre and Next for subsequent operations. Pre saves the node before head and next makes temporary changes. Otherwise, exit the loop, return pre, and the program ends. 3. First, assign the temporary variable next to the next value of head, so that the linked list will continue during the operation, go to 4; 4. Assign next to head to pre (the previous element of head), go to 5; 5. Assign pre to the current head value, go to 6. 6. Move head back one bit and assign the current value to next, go to 2.
Screenshot of submission result:
The recursive method
/ * *
* 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. The basic problem is solved
if(head == null || head.next == null) {
return head;
}
//2. Break big problems into smaller ones
ListNode reve = reverseList(head.next);
//3. Turn solutions of small problems into solutions of big problems
head.next.next = head;
head.next = null;
return reve;
}
}
Copy the code1, first look at the recursion header, which is the basic problem of the problem: if the incoming is empty or only one node, do not reverse the direct return can be; 2. Break big problems into smaller ones: just reverse the linked list of head. Next and the nodes after it; 3. Turn the solution of a small problem into the solution of a big problem: turn the next of the original head to head, and the next of the original head to empty. Screenshot of submission result:
These are the iterative and recursive solutions to reverse linked lists.
Welcome to attention
Scan the qr code below to pay attention:
