Carefully selected 9 linked list related algorithm questions, each given the corresponding answers and skills, after looking at these linked list problems, I believe you are not afraid of linked list problems, suggest like, favorites.
In order to facilitate you to find, I give a directory here
1. How to gracefully reverse single linked lists
2. Optimal solution of Joseph problem with circular singly linked list
3. Three ways to judge palindrome lists gracefully
Delete the middle node of the list
5. Divide the one-way list into the form of small on the left, equal in the middle and large on the right according to a certain value
6. Copy the linked list with random pointer nodes
7. Reverse the order between each K nodes of a singly linked list
8. Transform the search binary tree into a bidirectional linked list
Delete the KTH node in the list
More algorithm problems, we can also pay attention to my public number: helpless and painful code farmers, mainly write algorithm, computer basics and other articles, there have been more than 100 original articles
1. How to gracefully reverse single linked lists
【 topic description 】
Reverse a single linked list. For example, the linked list is:
1 – > 2 – > 3 – > 4
After inversion for
4 – > 3 – > 2 – > 1
【 for 】
If the length of the list is N, the time complexity is O(N), and the extra space complexity is O(1).
“Answer”
Method 1
This problem is quite simple, when we reverse a node, change a node’s back drive to point to its front. The important thing to note here is that when you point the back of the current node to the front, the linked list will be truncated, which means that the next node is separated from the current node, so we need a variable to hold the back of the current node in case of loss.
The specific code is as follows:
The following code
// Node class Node{public int value; public Node next; public Node(int data) { this.value = data; }}Copy the codePublic static Node reverseList(Node head) {Node next = null; // Node pre = null; // A precursor to the current nodewhile(head ! = null) { next = head.next; // Next = pre; pre = head; Head = next; }return pre;
Copy the codeMethod 2
This problem can also be done recursively, assuming that the function of the reverse() method is to reverse a single linked list. Using recursion, we can recurse over and over again to sublists. For example, for the following linked list:
We recurse to sublist 2->3->4, i.e. Node newList = reverse(head.next). The recursive result is as follows:
After the reverse, the sublist 2->3-> becomes 4->3->2. Note that I just assumed that the function of reverse() was to reverse lists. But node 1 still points to node 2. At this point, we reverse nodes 1 and 2 again, and then the next node of 1 points to NULL. As shown in figure:
The end condition of recursion is that the recursion ends when the sublist has only one node or is null. The code is as follows:
Public static Node reverseList2(Node head){public static Node reverseList2(Node head){if (head == null || head.next == null) {
returnhead; } // reverseList2 = reverseList2(head.next); Head. Next. Next = head; head.next = null;return newList;
}
Copy the codeProblems develop
Topic: Reverse partially linked list nodes
【 topic description 】
Given the head of a one-way linked list and two integers from and to, reverse the from and to parts on a single necklace list
Such as: 1 – > 2 – > 3 – > 4 – > 5 – > null, the from = 2, the to = 4
Results: 1 – > > 4-3 – > 2 – > 5 – > null
Such as:
1->2->3->null from=1,to=3
Results of 3 – > 2 – > 1 – > null
【 for 】
1. If the list length is N, the time complexity requirement is O (N), and the extra space complexity requirement is O (1).
2. If 1<=from<=to<=N is not met, no adjustment is made
“Answer”
This one just goes right out of the code
public static Node reversePart(Node head, int from, int to) { int len = 0; // Record the list length Node node1 = head; Node fPre = null; Node tPos = null; // point to the node to + 1while(node1 ! = null) { len++;if(len == from - 1)
fPre = node1;
if(len == to + 1) tPos = node1; node1 = node1.next; } // Determine whether the given value is reasonableif(from > to || from < 1 || to > len)
returnhead; Node1 = fPre == null? head : fPre.next; Node cur = node1.next; //cur points to the current node to be processed node1.next = tPos; Node next = null;while(cur ! = tPos) { next = cur.next; // Save the next node of the current node cur.next = node1; node1 = cur; cur = next; }if(fPre ! = null) { fPre.next = node1;return head;
}
return node1;
}
Copy the codeWant to learn the algorithm we can also pay attention to the public number “helpless and painful code farmers”, mainly write algorithm, computer basics and other articles, there have been more than 100 original articles oh.
2. Joseph problem for circular singly linked lists
【 topic description 】
【 for 】
Input: a circular unidirectional list of head nodes head and count m.
Return: the last surviving node, and this node itself forms a circular one-way list, other nodes are deleted.
“Answer”
Method 1: Time complexity O(n * m)
This is pretty easy if you don’t have to worry about the time, so you iterate through the list, and you delete one node for every m nodes, and you only have one node left in the list.
The following code
Public static Node josephusKill(Node head, int m) {public static Node josephusKill(Node head, int m) {if(head == null || m < 1)
returnhead; Node last = head; // Locate the last nodewhile(head.next ! = last) { head = head.next; } System.out.println(head.value); int count = 0;while(head.next ! = head) {if (++count == m) {
head.next = head.next.next;
count = 0;
} else{ head = head.next; }}return head;
}
Copy the codeThe time complexity of this method is O(n * m). Let’s use time complexity as the solution.
Method 2: Time complexity is O(n)
The difficulty of this method is:
Painted painted school: u do
We can number the nodes of the circular linked list. If the number of nodes in the linked list is N, the first node is numbered 1, the next node is 2, and the last node is n.
We use f(n) to indicate that when the length of the circular list is n, the number of people who survive is F (n), and obviously when n = 1, f(n) = 1. If we can figure out the relationship between f(n) and f(n-1), then we can do it recursively. Let’s say the number of people is n, and the person who counts to M commits suicide. The initial number is
.
m – 2
m – 1
m
m + 1
m + 2
.
After a delete, node M is deleted. After deletion, there are only n-1 nodes left, and the conversion relationship between the numbers before and after deletion is as follows:
Before deleting ——– after deleting
. — — — — — — — — — -…
m – 2 ——- n – 2
m – 1 —— n – 1
M ———- None (because the number was removed)
M + 1 —— 1(because I will count from here next time)
m + 2 —— 2
. — — — — — — — –…
The new ring has only n minus 1 nodes. And nodes numbered m + 1, M + 2, and M + 3 become nodes numbered 1, 2, and 3 in the new ring.
Assuming that old is the node number before deletion and new is the node number after deletion, the relationship between old and new is old = (new + m-1) % n + 1.
Old = (new + m) % n Mainly because the numbers start at 1, not 0. If new + m == n, the result will be old = 0. So old = (new + m – 1) % n + 1.
So that gives us the relationship between f(n) and f(n – 1), and f(1) = 1. So we can do it recursively.
The code is as follows:
Public static Node josephusKill2(Node head, int m) {public static Node josephusKill2(Node head, int m) {if(head == null || m < 1)
returnhead; int n = 1; // Count how many nodes there are.while(last.next ! = head) { n++; last = last.next; Int des = f(n, m); // Fetch the destination nodewhile(--des ! = 0) { head = head.next; } head.next = head;return head;
}
private static int f(int n, int m) {
if (n == 1) {
return 1;
}
return (getDes(n - 1, m) + m - 1) % n + 1;
}
Copy the codeProblems develop
For the last problem, what if we were to count the deletions from the KTH node? And how to solve it?
3. Three ways to judge palindrome lists gracefully
【 topic description 】
Given the head node of a linked list, determine whether the list is palindromic.
Such as:
1->2->1, returns true.
1->2->2->1, returns true.
1->2->3 returns false.
【 for 】
If the length of the list is N, the time complexity reaches O(N).
“Answer”
Method 1
We can make use of the stack to assist us by pushing all the nodes of the linked list onto the stack and comparing them with the linked list one by one. For example, for the linked list 1->2->3->2->2, the following figure is shown after the push:
This solution is relatively simple, the time complexity is O(n), space complexity is O(n).
The following code
Public static Boolean f1(Node head) {if (head == null || head.next == null) {
return true;
}
Node temp = head;
Stack<Node> stack = new Stack<>();
while(temp ! = null) { stack.push(temp); temp = temp.next; }while(! stack.isEmpty()) { Node t = stack.pop();if(t.value ! = head.value) {return false;
}
head = head.next;
}
return true;
}
Copy the codeMethod 2
Do you really need to push them all? In fact, we can also make the last half of the linked list to be pushed, and then compare the elements in the stack with the first half of the linked list, for example, 1->2->3->2->2 ->2 after the last half of the list is pushed:
Then, stack by stack and compare with the first half of the linked list (1->2). If you do that, you cut the space complexity in half.
The code is as follows:
Public static Boolean f(Node head) {if(head == null || head.next == null)
return true; Node slow = head; // Node fast = head; // Stack<Node> Stack = new Stack<>(); // Slow ends up pointing to the middle nodewhile(fast.next ! = null && fast.next.next ! = null) { slow = slow.next; fast = fast.next.next; } System.out.println(slow.value); slow = slow.next;while(slow ! = null) { stack.push(slow); slow = slow.next; } // Make a judgmentwhile(! stack.isEmpty()) { Node temp = stack.pop();if(head.value ! = temp.value) {return false;
}
head = head.next;
}
return true;
}
Copy the code** Method three: ** space complexity is O(1).
We can reverse the second half of the linked list, and then compare the second half with the first half. This only requires O(1) in extra space and O(n) in time.
The code is as follows:
Public static Boolean f2(Node head) {if(head == null || head.next == null)
return true; Node slow = head; // Node fast = head; // Fast pointer //slow ends up pointing to the middle nodewhile(fast.next ! = null && fast.next.next ! = null) { slow = slow.next; fast = fast.next.next; } Node revHead = reverse(slow.next); // Reverse the second half // comparewhile(revHead ! = null) { System.out.println(revHead.value);if(revHead.value ! = head.value) {return false;
}
head = head.next;
revHead = revHead.next;
}
return true; } private static Node reverse(Node head) {if (head == null || head.next == null) {
return head;
}
Node newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Copy the codeProblems develop
Consider: If you are given a circular linked list and a head node is specified, how can you tell if it is a palindrome list?
4, : Delete the middle node of the single linked list
【 topic description 】
Given the head node of the linked list, implement the function to delete the middle node of the linked list.
Such as:
Step remove any node;
1->2, delete node 1.
1->2->3: delete node 2.
1->2->3->4: Delete node 2.
1->2->3->4-5 delete node 3.
【 for 】
If the length of the list is N, the time complexity is O(N), and the extra space complexity is O(1).
“Answer”
This problem requires that the intermediate node be removed. We can do this using the double-pointer method, which uses a fast pointer and a slow pointer. The fast pointer advances two nodes at a time, and the slow pointer advances one node at a time. When the fast pointer traverses the node, the slow pointer happens to be in the middle node. I wrote a little bit earlier about some of the tricks that algorithms use and some of the tricks that Pointers use.
However, when doing this, it is best to handle some special cases first, such as deleting the first node, or not deleting the node (only one node is not deleted).
The following code
public static Node removeMidNode(Node head) {
if(head == null || head.next == null)
return head;
if (head.next.next == null) {
returnhead.next; } Node fast = head.next.next; // slow = head; // Slow ends up pointing to the precursor of the intermediate nodewhile(fast.next ! = null && fast.next.next ! = null) { slow = slow.next; fast = fast.next.next; } // Delete slow.next = slow.next-next;return head;
}
Copy the codeIn fact, the problem of deleting the KTH node from last time could also use double Pointers, but in my opinion, the method of using double Pointers in that problem is not as elegant as the one I did last time, while the method of deleting the middle node this time is more elegant. As for the reason, you can type the code to see
Problems develop
Topic: Delete the node at A/B in the linked list
【 topic description 】
Given the head nodes of the linked list, head, integers A and b, implement the function to delete nodes located at a/b.
Such as:
Linked list: 1->2->3->4->5, assuming a/b has the value r.
If r = 0, no nodes are deleted;
If r is in the interval (0,1/5), delete node 1;
If r is on the interval (1/5,2/5), delete node 2;
If r is on the interval (2/5,3/5), delete node 3;
If r is on the interval (3/5,4/5), delete node 4;
If r is on the interval (4/5,1), delete node 5;
If r is greater than 1, no nodes are removed.
【 for 】
If the length of the list is N, the time complexity is O(N), and the extra space complexity is O(1).
“Answer”
You can do it yourself or you can think about it, I’ll just throw away the code
// delete the K = (a * n/b) node. Where n represents the number of linked list nodes //, but since (a * n/b) may have decimals, we take the upper limit of K. // Upper bound is the smallest integer greater than or equal to K. public static Node removeByRatio(Node head, int a, int b) {if(a < 1 || a > b)
returnhead; int n = 0; Node cur = head; // Count how many nodes there arewhile(cur ! = null) n++; Int K = (int) math.ceil ((double)(a * n)/(double)b); int K = (int) math.ceil (a * n)/(double)b);if(K == 1)
return head.next;
if(K > 1) { cur = head; // Locate the KTH node's precursorwhile(--K ! = 1) { cur = cur.next; } cur.next = cur.next.next; }return head;
}
Copy the codeFinally, to promote my public number: helpless and painful code farmers, mainly write algorithms, computer basics and other articles, which have more than 100 original articles
5. Divide the one-way linked list into the form MD of small on the left, equal in the middle and large on the right according to a certain value
【 topic description 】
Given a one-way linked list, head, the value of the node is an integer, and an integer privot. Implement a function to adjust the list so that the left part of the list is less than privot, the middle part is equal to privot, and the right part is greater than Privot. And there is no requirement on the order of some internal nodes
For example: linked list 9-0-4-5-1, pivot=3.
Adjusted to 1-0-4-9-5,
It could be 0-1-9-5-4
【 for 】
If the length of the list is N, the time complexity reaches O(N).
“Answer”
This problem is relatively simple in the way of thinking, but there are still some details that need to be major in the implementation.
An easy way to do this is to use an array to store the nodes of a linked list, and then divide them by some value like a quicksort partition function.
But if I do that, it’s order N. We can also use three Pointers to divide the original linked list into three parts in turn, and then combine them. This approach not only has O(1) space complexity, but also the order of internal nodes is the same as the original linked list. Although the idea is simple, but in the code implementation is also a lot of details need to pay attention to, if there is time, I hope you start to lay down the code.
The following code
Public static Node listPartition(Node head, int pivot) {Node sB = null; // Small begin Node sE = null; // Small end Node eB = null; // Equal begin Node eE = null; Emall end Node bB = null; Big begin Node bE = null; // Big end Node next = null; // Save the next node // partitionwhile(head ! = null) { next = head.next; head.next = null;if (head.value < pivot) {
if (sB == null) {
sB = head;
sE = head;
} else{ sE.next = head; sE = sE.next; }}else if (head.value == pivot) {
if (eB == null) {
eB = head;
eE = head;
} else{ eE.next = head; eE = eE.next; }}else {
if (bB == null) {
bB = head;
bE = head;
} else{ bE.next = head; bE = bE.next; } } head = next; } // if () {// if () {// if () {// if () { Small and in seriesif(sB ! = null) { sE.next = eB; eE = eE == null ? sE : eE; } //2. Medium and large connectionsif(eB ! = null) { eE.next = bB; }returnsB ! = null ? sB : eB ! = null ? eB : bB; }Copy the codeIt is not easy to organize, and it is not easy to write these articles. If you find this article inspiring, in order to let more people see this article: might as well
1, like, so that more people can see this content (collection does not like, are playing rogue -_-)
Pay attention to me and column, let us become a long-term relationship
3, pay attention to the public number “helpless and painful code farmers”, mainly write algorithm, computer basics and other articles, which have more than 100 original articles
