Learn these list algorithm questions, interviews are no longer afraid of handwritten list
The author’s writing skill is still shallow, if there is something wrong, please point out generously, will be grateful
I am often asked to write the code for linked lists by hand in interviews. The following are some of the questions I have been asked in interviews. Of course, I’m not going to write the optimal solution, but if there’s a better solution, you’re welcome to point it out.
So let me just list them for you to see
- Delete the NTH last node in the linked list
- List inversion
- Merges two ordered lists
- Find the middle node of the list
We must be in the computer hand knock again, it is best to hand write on the paper
Delete the NTH last node in the linked list
Given a linked list, delete the NTH last node of the list and return the first node of the list.
1Given a linked list: 1->2->3->4->5, and n = 2.
2
3When the penultimate node is deleted, the list becomes 1->2->3->5.
Copy the codeIn linked list problems, sometimes a pointer won’t solve a problem and we’ll just add another pointer. In general, two Pointers will solve most problems
Above is the linked list we define. For example, if we want to delete the NTH node from the penultimate, we define two Pointers, one fast and one slow. The fast pointer is N steps faster than the slow pointer, and then the fast and slow Pointers move forward together, so that when the fast pointer reaches Null, the slow pointer points to the node we want to delete.
For example, if we want to delete the penultimate node, the initialization pointer points to the following.
After iterating over the pointer, we can see that the pointer on the left points to the node we want to delete
Part of the code is as follows
1public void deleteNodeForN(Node head, int n){
2
3 Node left = head;
4 Node right = head;
5 int i = 0;
6 while(right! =null && i < n){
7 right = right.getNext();
8 i++;
9 }
10
11 while(right! =null) {
12 left = left.getNext();
13 right = right.getNext();
14 }
15 // Delete the left node after traversing
16 deleteNode(left);
17
18}
Copy the codeList inversion
Topic: Reversing a singly linked list.
1Input:0->1->2->3->4->5->NULL
2Output:5->4->3->2->1->0->NULL
Copy the codeThere is no problem in a linked list that can’t be solved by adding a pointer. If there is, add another pointer.
Solution one: add pointer
We added two Pointers to delete the NTH node in the list above, so what do we do if we want to reverse the list? Two Pointers are no longer enough; we need three Pointers to define the current node, the node before the current node, and the node after the current node. Of course, this way is neither take up space, time is also a fast solution.
We’re defining a linked list, so what do we want Pointers to look like? So I’m going to show you step by step how to flip a list with three Pointers, and you don’t have to look at my final solution, but you can look at my diagram and write your own code, and see if you can do that.
Part of code display
1public Node reversalNodeThree(Node head) {
2 if (head == null || head.getNext() == null) {
3 return head;
4 }
5
6 Node preNode = null;
7 Node nextNode = null;
8 while(head ! =null) {
9 nextNode = head.getNext();
10 head.setNext(preNode);
11 preNode = head;
12 head = nextNode;
13 }
14 return preNode;
15}
Copy the codeSolution two: recursion
The key to recursive code is how to break down big problems into smaller ones, write recursive formulas based on that, and then refine termination conditions.
When we write recursive code, we should not think step by step inside the set, the set itself will be easy to confuse. In fact, the essence of recursion is to break down small tasks, and the correct way of thinking is to block out the details of recursion, assume that the result is already what we want, and then just think about the first step.
Let’s take the reverse linked list as an example of how to think recursively, and how to turn our thinking into code.
Here the next node to node 0 is not node 5, but the big node in our gray background
In the case of the linked list above, we want to reverse, assuming that the first node and all subsequent nodes have been successfully reversed, what do we do next? I believe that you can do it here, which is the transformation of two nodes.
1Node(0).getNext(a).setNext(Node(0));
2Node(0).setNext(null);
Copy the code- Terminating condition: When the passed Node is null or the passed Node.next is null. Indicates that an empty node or only one node is passed in, and no inversion is required
Using the termination conditions above and the analyzed code, we can write the following recursively reverse a chain of code.
1public Node reversalNodeTwo(Node head){
2
3 if (head == null || head.getNext() == null) {
4 return head;
5 }
6
7 Node reHead = reversalNodeTwo(head.getNext());
8
9 head.getNext().setNext(head);
10
11 head.setNext(null);
12
13 return reHead;
14
15}
Copy the codeMerges two ordered lists
Title: Merge two ordered lists into a new ordered list and return. A new list is formed by concatenating all the nodes of a given two lists.
1Input: 1->2->4, 1->3->4
2Output: 1 - > 1 - > 2 - > 3 - > 4 - > 4
Copy the codeThe iteration
Joining two lists iteratively is done by using Pointers. Join us now we have the following two linked lists. We will define two Pointers to the head of each list to start a one-by-one comparison, with the smaller party moving the node out and the pointer backwards. Until null. Next we break down each step with images. You can code according to the prompts of the picture, the answer is attached.
Part of code display
1public Node mergeTwoListTwo(Node nodeOne, Node nodeTwo){
2
3 AboutLinkedList mergeTwoList = new AboutLinkedList();
4 Node headNodeOne = nodeOne;
5 Node headNodeTwo = nodeTwo;
6
7 while(headNodeOne! =null|| headNodeTwo! =null) {
8
9 if (headNodeOne == null || headNodeOne.getNum() > headNodeTwo.getNum()){
10 mergeTwoList.addNode(headNodeTwo);
11 Node pre = headNodeTwo;
12 headNodeTwo = headNodeTwo.getNext();
13 pre.setNext(null);
14 }else {
15 mergeTwoList.addNode(headNodeOne);
16 Node pre = headNodeOne;
17 headNodeOne = headNodeOne.getNext();
18 pre.setNext(null);
19 }
20 }
21 return mergeTwoList.head.getNext();
22}
Copy the codeFind the middle node of the list
Title: Find the middle node of a linked list
1Input: 0 - > 1 - > 2 - > 3 - > 4
2Output: 2
Copy the codePointer to the
In general, linked list problems we can use Pointers, whether it is time or space is the best solution, in fact, there is a small trick, is to define two Pointers (fast Pointers), fast Pointers go two nodes each time, slow Pointers go one node each time. So when the fast pointer gets to the end the slow pointer gets to the middle. Now let’s use the diagram to get a better sense of how the pointer moves. You can write your own code as shown here, and then look at the code I gave you at the end. It will be more memorable
Part of code display
1public Node getNodeForCenter(Node head){
2 if (head == null) {
3 return null;
4 }else if (head.getNext() == null) {
5 return head;
6 }
7 Node slow = head;
8 Node fast = head;
9 while(fast! =null&& fast.getNext()! =null) {
10 slow = slow.getNext();
11 fast = fast.getNext().getNext();
12 }
13 return slow;
14}
Copy the codeFinally remind, we must be in the computer hand knock again, it is best to hand write on the paper again