For a program ape, the importance of data structure and algorithm will not need me to say more, algorithm has become a big factory test interview now the highlight, nonsense less to say, Leetcode brush up. When it comes to brushing Leetcode, I suggest you stick to tag, otherwise you’ll end up like a headless chicken. Recently, I happened to brush the linked list questions on Leetcode, and also encountered some representative questions. I just want to make a record and share it with friends who need it.
People who are not familiar with linked lists may feel at a loss when they encounter linked lists. Compared with arrays, linked lists are indeed more abstract and require a certain amount of spatial imagination, especially when some Pointers poke and poke, which can easily confuse people. At this point, you might as well take out a pen and paper and draw a simple diagram, which will help you solve the linked list problem. This article will illustrate the three list inversion algorithm problems, which correspond to the difficulty levels of simple, medium and difficult in Leetcode respectively. It is a relatively representative question type, which is of great reference significance for solving linked list problems.
1, Leetcode 206Reverse Linked List(Difficulty: Easy)
The title description is as follows:
Solution one, iterative inversion
Take a look at the schematic diagram, using linked list 1->2->3->4->5 as an example:
Diagram of single linked list iteration inversion
When iterating through a linked list, there are only three things to do each time: 1. Place the next pointer of the current node to its predecessor; 2. 2. Point the precursor node pointer to the current node. 3. Point the pointer to the current node to the next node. Note that we need a variable to hold the next node of the current node, which we call temp. The code is as follows
public ListNode reverseList(ListNode head) {
// The precursor node is initially null
ListNode prev = null;
// The current node is represented by cur
ListNode cur = head;
// Use temp to hold the next node
ListNode temp;
while(cur ! =null) {
// Get the next node
temp = cur.next;
// Place the next pointer of the current node to its predecessor
cur.next = prev;
// Point the precursor node pointer to the current node
prev = cur;
// Point the current node pointer to its next node
cur = temp;
}
// Notice that prev is returned at the end
return prev;
}
Copy the codeSolution two, recursive inversion
A lot of questions can be written fairly succinctly with recursion, but recursion is not as easy to understand as iteration. So far, I’ve only been able to recursively solve some fairly basic problems, like this one. It’s easy to get bogged down in details when it comes to recursion problems, but no smart mind can fit multiple recursive stacks, so focus on subproblems and termination conditions. This time, we’ll start with the code and then figure it out
public ListNode reverseList(ListNode head) {
The recursive termination condition is that the current node is empty, or the next node of the current node is empty
// The last node of a singly linked list is returned
if(head == null || head.next==null) {
return head;
}
// Delegate the task of reversing the list of children after the current node to the child procedure
// It is enough to know that the subprocedure can reverse the sublist
ListNode p = reverseList(head.next);
// Now that the sublist has been reversed, the next step is to deal with the relationship between the sublist and the current node
// The following two steps should be understood according to the schematic diagram
head.next.next = head;
// To prevent list loops, head. Next needs to be left blank
head.next = null;
// Each level of the recursive function returns p, the last node of the initial list
return p;
}
Copy the codeAssuming the list is 1->2->3->4->5, the following is a diagram of the recursive process.
Diagram of recursion inversion of a single linked list
Here’s another comment from Leetcode’s topic board, hopefully to help you understand recursion.
Suppose the linked list is 1,2,3,4,5. In reverseList(4), 5-> Next = 4, 4-> Next = null. In reverseList(4), 5->next = null. ReverseList (3) = 4->next = 3,3->next = NULL 5 – > 4 – > 3 – > null, reverseList (2), reverseList so on (1), p is: 5 – > 4 – > 3 – > 1 – > 2 – > null.
2, Leetcode 92Reverse Linked List II(Difficulty: Medium)
The title description is as follows:
- Add dummy to the list so that you don’t need to worry about the head node alone.
- Find the linked list interval to be operated. The start node of the interval is represented by start, and the end node is represented by End.
- To operate the linked list on the interval;
- To rejoin the operated list back to the original list, here we need two more variables, the prev and the successor.
This completes all operations and returns dummy.next, as shown below
Diagram of interval inversion of a singly linked list
Then add the code:
public ListNode reverseBetween(ListNode head, int m, int n) {
// Add a virtual head node
ListNode dummy = new ListNode(0);
dummy.next = head;
// The precursor node
ListNode prev = dummy;
// Invert the interval start node
ListNode start = head;
// Reverse the interval end node
ListNode end = head;
// Subsequent nodes
ListNode successor;
// The first for loop finds the precursor node and the interval start node
for (int i = 1; i < m; i++) {
prev = prev.next;
start = start.next;
end = end.next;
}
// The second for loop finds the interval end node
for (int i = m; i < n; i++) {
end = end.next;
}
// Find the successor node
successor = end.next;
// A crucial step is to disconnect the last node of the inversion interval from the original list, otherwise it will cause an infinite loop
end.next = null;
// reverseList() can be used to reverse a single linked list
prev.next = reverseList(start);
// After the reverse, start becomes the end node and joins it to its successors
start.next = successor;
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp;
while(cur ! =null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
Copy the code3, Leetcode 25Flip linked lists in groups of K(Difficulty: difficulty)
The title description is as follows:
The operation is performed on a list of intervals. The difference is that the operation is performed on multiple intervals in a row. It seems impossible to start.
A group of K reverse chains indicates intent
The code is as follows:
public ListNode reverseKGroup(ListNode head, int k) {
// Add a virtual header
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode start = head;
ListNode end = head;
ListNode successor;
while(end ! =null) {
// Loop k times to determine the interval to be reversed
for (int i = 1; i < k && end ! =null; i++) {
end = end.next;
}
// If the end node is empty, the number of nodes to be reversed is less than K
if (end == null) {
break;
}
successor = end.next;
// The crucial step is to break the last node of the list to be reversed from the subsequent list
end.next = null;
// Reverse the list and join the reversed list header after the prev
// reverseList() is the same as reverseList()
prev.next = reverseList(start);
// Start, after the antecedent, becomes the end node to link it with the antecedent
start.next = successor;
// Reassign the variables below, then proceed to the next loop
prev = start;
start = successor;
end = successor;
}
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp;
while(cur ! =null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
Copy the code4, summarize
To sum up, many linked list problems can be simplified by adding virtual head nodes. For interval operation, you can consider using variables such as precursor, successor, start and end. In addition, you should draw more with pen, because it will be more intuitive to the eyes.
Emma finally finished, these pictures really exhausted me, just to make a note to deepen the impression, also hope to help friends in need.