preface:
Hello, everyone. Today is the eighth day of LeetCode's daily question. What I share is the reversal of the linked list and the difficulty coefficient of two stars! No more nonsense, let's start with the topic!
1.1 subject requirements
Topic type: linked list inversion
Title Content: reverse the link order of the single linked list
Test case:
Input: 1 - > 2 - > 3 - > 4 - > 5
Output: 5 - > 4 - > 3 - > 2 - > 1
Note: use two ways to solve the problem!
1.2 problem solving methods
The above mentioned implementation of linked list inversion uses two ways to solve problems. What are these two ways? Let's keep looking down!
1.2. 1 use iterative method
1. Problem solving ideas
Core idea: repeat a process, and the result of each processing is used as the initial value of the next processing. These initial values are similar to the state, and each processing will change the state until the final state is reached
General idea:
- Traverse the linked list from front to back and point the next of the current node to the previous node. Therefore, a variable prev is required to store the previous node;
- After the current node is processed, you need to find the next node, so you need a variable curr to save the current node;
- After processing, assign curr (current node) to prev (previous node) and assign the next pointer to curr (current node). Therefore, a temporary variable is required to save the next pointer of the next node in advance
Linked list inversion process:
- Save the next pointer of curr (current node) to the next temporary variable, that is, next = curr next
- Assign prev (previous node) to the next pointer of curr (current node), i.e. curr next = prev
- The curr (current node) in this round of processing becomes prev (previous node) in the next round of node processing, that is, prev = curr;
- After this round of processing, assign next (temporary variable) to curr (current node) of the next round of node processing, that is, curr = next;
1.2. 2 code implementation
1. Initial preparation
- Test code
package com.kuang.leetcode1;
/**
* @ClassName ReverseList1
* @Description Linked list inversion - use iterative method
* @Author Galloping snail rz
* @Date 2021/8/26
*/
public class ReverseList1 {
public static void main(String[] args) {
//Initialize 5 linked list nodes, and specify the current value of val and the next pointing node
//Node 5
ListNode node5 = new ListNode(5, null);
//Node 4
ListNode node4 = new ListNode(4, node5);
//Node 3
ListNode node3 = new ListNode(3, node4);
//Node 2
ListNode node2 = new ListNode(2, node3);
//Node 1
ListNode node1 = new ListNode(1, node2);
//Use the iterative method to reverse the linked list (the head node is node1)
ListNode prev = iterate(node1);
//Print prev node values
System.out.println(prev);
}
//Static internal class listnode (linked list node)
static class ListNode {
int val; //Corresponding value of current node
ListNode next; //Next pointer to the next linked list node
/**
* ListNode Parameterized constructor
* @param val Current node value
* @param next Next linked list node
*/
public ListNode(int val, ListNode next) {
//Initialize current value
this.val = val;
//Initialize next node
this.next = next;
}
}
/**
* Iterative inversion of linked list elements
* @param head Chain header node
* @return ListNode struct Node
*/
public static ListNode iterate(ListNode head) {
//prev is the previous node in the linked list (1 is the head node, and its previous node value is null), and next is the temporary variable for storing the next node
ListNode prev = null, next;
//curr refers to the current node (header node)
ListNode curr = head;
/**
* When it comes to iteration (or loop traversal), do you use a for loop or a while loop?
* Because the length of the linked list is unknown, the for loop cannot be used for finite cycles,
* The current iterative method has only one head parameter, which only contains the value of the head node and the next pointer,
* It does not contain iterators, and the bottom layer of the for loop depends on iterators, so the while loop is used
*/
/**
* So what is the execution condition of the while loop?
* curr(When the current node) value is null, it indicates that the last element of the linked list has been executed,
* As long as the curr value is not null, the proof needs to continue the loop
* Therefore, the execution condition of the while loop is that the current node value is not null (i.e. curr! = null)
*/
while (curr != null) {
//Assign next (next node, value 2) of curr (current node, value 1) to next (temporary variable)
next = curr.next;
//Assign prev (previous node, initial value is null) to next (next node) of curr (current node, value is 1)
curr.next = prev;
//Reassign pre and curr in preparation for processing the next node
//Curr (current node, value 1) in this round of processing becomes prev (previous node) in the next round of node processing
prev = curr;
//After this round of processing, assign next (temporary variable, value 2) to curr (current node) of the next round of node processing
curr = next;
}
//Return the prev variable (at this time, the value of the variable is the current node in the previous cycle)
return prev;
}
}
Note: if there is no idea when writing algorithm problems, you can first write a general code framework according to the problem stem, and then supplement the code after careful analysis of the problem stem and further debugging
-
Debug test
Break the last two lines of code in the main method, and then Debug them in turn
- test result
Before reversing the linked list:
After the linked list is reversed:
Results: the linked list was successfully reversed!
1.2. 2 use recursive method
1. Problem solving ideas
Core idea:
-
Repeat in a similar way, similar to the tree structure. First find the leaf node from the root node and traverse from the leaf node;
-
The large problem (the whole linked list) is divided into small problems with the same nature (the inversion of two elements), namely curr next. next = curr,
After all the small problems are solved, the big problems are solved
Problem thinking:
Suppose 1 is the head node, the next value of 1 is 2, and the next value of 2 is 3; If you want to reverse the linked list, you need to break the next pointer pointing to 3 and let the next pointer of 2 point to 1. How to achieve it?
Solution:
Therefore, you need to set a next temporary variable to store head Next (value is 2), i.e. head next. next = head = 1;
However, after the next pointer of 2 points to 1, the next pointer of 1 also points to 2, which will form a ring linked list. How to solve it?
Solution:
Let the next pointer of head node 1 point to null, that is, head next = null
Similarly, if starting from the end of the linked list, the next pointer of the current node 5 points to 4, and the next pointer of 4 points to null, but the next pointer of 3 is not disconnected and still points to 4, so the position of 4 can be determined
Key points:
- You just need to execute curr. XML for each element next. next = curr, curr. Next = null two steps
- In order to keep the linked list open, you must start with the last element
2. Code implementation
- Test code
package com.kuang.leetcode1;
/**
* @ClassName ReverseList1
* @Description Linked list inversion - use recursion
* @Author Galloping snail rz
* @Date 2021/8/26
*/
public class ReverseList2 {
public static void main(String[] args) {
//Initialize 5 linked list nodes, and specify the current value of val and the next pointing node
//Node 5
ListNode node5 = new ListNode(5, null);
//Node 4
ListNode node4 = new ListNode(4, node5);
//Node 3
ListNode node3 = new ListNode(3, node4);
//Node 2
ListNode node2 = new ListNode(2, node3);
//Node 1
ListNode node1 = new ListNode(1, node2);
//Use recursive method to reverse the linked list (the head node is node1)
ListNode prev = recursion(node1);
//Print prev node values
System.out.println(prev);
}
//Internal class ListNode
static class ListNode {
int val; //Current node value
ListNode next; //Next pointer to the next node
/**
* ListNode Parameterized constructor
* @param val Current node value
* @param next Next linked list node
*/
public ListNode(int val, ListNode next) {
//Initializes the current value and the next node
this.val = val;
this.next = next;
}
}
/**
* Recursive inversion of linked list elements
* @param head Chain header node
* @return ListNode struct Node
*/
public static ListNode recursion(ListNode head) {
/**
* Question 1: what are the conditions for stopping recursion?
* If the head value is null (indicating that the linked list is empty, so there is no need to reverse),
* Or the next value of the head node is null (indicating that the last element is recursive)
*/
if(head == null || head.next == null) {
//Finally, the head (head node) is returned
return head;
/**
* Question 2: why return the head node?
* If the head node is null, the current linked list is empty and no inversion is required;
* If the next value of the head node is null, it indicates that the last element has been recursive, so the current head node is returned
*/
}
//Recursion is calling itself
//Assuming that the head node value is 4, then head The value of the next node is 5. After recursion, new is returned_ The head node value is also 5
ListNode new_head = recursion(head.next);
//The next pointer of the head node points to the next node as the head node
head.next.next = head;
//The next value of the head node is null
head.next = null;
//Return the new header node
return new_head;
/**
* Question 3: what is the final return value?
* When the fifth node (value 5) recurses, its next value is null,
* Therefore, the stop condition of recursion (head.next=null) is satisfied and execution will not continue;
* After reversing the linked list, you also need to return the head node (at this time, the value is 5)
*/
}
}
-
Debug test
Break the last two lines of code in the main method, and then Debug them in turn
- test result
Before reversing the linked list:
After the linked list is reversed:
Results: the linked list was successfully reversed!
Well, today's LeetCode daily question - linked list inversion ends here. Welcome to learn and discuss, praise and collect!
Reference video link: https://www.bilibili.com/video/BV1Ey4y1x7J3 (50 lectures on domestic algorithm dictionary LeetCode algorithm)