This note was sorted out for a whole week. Each line of code was written by itself and the test was successfully run. At the same time, I also reviewed the explanations related to the linked list in the book "Sword-pointing Offer". I hope to have some information about the written test and interview. help.
This article contains the following contents of the linked list:
1. Creation and traversal of single linked lists
2. Find the number of nodes in a single linked list
3. Find the k-last node in a single linked list (sword pointing to offer, question 15)
4. Find the intermediate nodes in a single linked list
5. Merge two ordered single linked lists, and the combined linked lists are still in order [high frequency of occurrence] (Step by the offer, Question 17)
6. The reversal of single-linked list [the highest frequency of occurrence] (Step by the offer, question 16)
7. Print a single linked list from the end to the beginning (sword pointing to offer, question 5)
8. Determine whether a single linked list has a ring
9. Take out the length of the ring in the linked list
10. In the single linked list, take out the starting point of the ring (sword pointing to offer, question 56). This question needs to use questions 8 and 9 above.
11. Determine the first intersection point of the intersection between two single-linked lists (sword pointing to offer, question 37)
1. Creation and traversal of single linked lists:
public class LinkList { public Node head; public Node current; //Method: Add data to the linked list public void add(int data) { //When judging that the linked list is empty if (head == null) {//If the header node The point is empty, which means that the linked list has not been created yet. Then assign the new node to the head node head = new Node(data); current = head; } else { //Create a new node and place it in the current node behind (correlate the new node with the linked list) current.next = new Node(data); //Move the current index of the linked list one by one, current = current.next; //After this operation is completed, current The node points to the newly added node} } //Method: traverse the linked list (print out the linked list. The parameters of the method indicate that traversal starts from the node node public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } class Node { //Note: The permissions of the two member variables here cannot be pri vate because private permissions are only accessible to this class. int data; //Data domain Node next;//Pointer domain public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list = new LinkList(); //Add data to LinkList for (int i = 0; i < 10; i++) { list.add(i); } list.print(list.head);// From The head node starts traversing the output} }In the above code, the Node node here uses an internal class to represent it (lines 33). The biggest advantage of using inner classes is that they can access each other private operations with outer classes.
Note: The characteristics of internal class access are: internal classes can directly access members of external classes, including private ones; external classes must first create objects if they want to access members of internal classes.
To facilitate the addition and traversal operations, add a member variable current to the LinkList class to represent the index of the current node (line 03).
In the method of traversing the linked list (line 20), the parameter node means that it starts from the node node, and does not necessarily need to traverse from the head node.
2. Find the number of nodes in a single linked list:
Pay attention to check whether the linked list is empty. The time complexity is O(n). This is relatively simple.
Core code:
//Method: Get the length of the single linked list public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length th++; current = current.next; } return length; }3. Find the k-last node in a single linked list:
3.1 Ordinary ideas:
First, iterate the entire linked list from beginning to end, calculate the length size of the linked list, and get the length of the linked list, it is easy to do. Just output the (size-k) node directly (note that the linked list is empty, k is 0 , k is 1, k is greater than the number of nodes in the linked list
). The time complexity is O(n), and the general idea is as follows:
public int findLastNode(int index) { //index represents the node of the index to the end.//The first time I traversed, I got the length of the linked list if (head == null) { return -1; } current = head; while (current != null) { size++; current = current.next; } //The second traversal is used to output data of the index node to the end. Current = head; for (int i = 0; i < size - index; i++) { current = current.next; } return current.data; }What should I do if the interviewer does not allow you to traverse the length of the linked list? Next is.
3.2 Improvement ideas: (This idea is also used in other questions)
Here you need to declare two pointers: that is, the two node-type variables first and second. First, let first and second point to the first node, and then let the second node move k-1 position backwards. At this time, first and Second is separated by k-1 positions, and then the two nodes are moved backward as a whole until the second node reaches the last node, the position pointed to by the first node is the position of the k-th until the last node. Time complexity is O(n)
Code implementation: (first version)
public Node findLastNode(Node head, int index) { if (node == null) { return null; } Node first = head; Node second = head; //Let the second node be indexed backwards Position for (int i = 0; i < index; i++) { second = second.next; } //Let the first and second nodes move backwards as a whole until the second node is Null while (second != null) { first = first.next; second = second.next; } //When the second node is empty, the node pointed to by first at this time is the node we are looking for return first; }Code implementation: (final version) (throw an exception when k is greater than the number of nodes in the linked list)
In the above code, the function seems to have been implemented, but it is not robust enough:
Pay attention to the situation where k is equal to 0;
If k is greater than the number of nodes in the linked list, a null pointer exception will be reported, so a judgment is needed here.
The core code is as follows:
public Node findLastNode(Node head, int k) { if (k == 0 || head == null) { return null; } Node first = head; Node second = head; //Let the second node move backwards k- 1 position for (int i = 0; i < k - 1; i++) { System.out.println("i's value is" + i); second = second.next; if (second == null) { / /Indicate that the value of k is already greater than the length of the linked list //throw new NullPointerException("The length of the linked list is less than" + k); //We throw an exception ourselves to give the user a prompt to return null; } } //Let first and second The node moves backward as a whole until second reaches the last node while (second.next != null) { first = first.next; second = second.next; } //When the second node reaches the last node At this time, the node pointed to by first is the node we are looking for. Return first; }4. Find the intermediate nodes in a single linked list:
Similarly, the interviewer does not allow you to calculate the length of the linked list. What should I do?
Idea:
Like the second section above, two pointers are set first and second, but here, the two pointers move forward at the same time, the second pointer takes two steps each time, and the first pointer takes one step each time until the second pointer reaches At the last node, the node pointed to by the first pointer is the intermediate node. Note that the linked list is empty and the number of nodes of the linked list is 1 and 2. The time complexity is O(n).
Code implementation:
//Method: Find the intermediate node of the linked list public Node findMidNode(Node head) { if (head == null) { return null; } Node first = head; Node second = head; //Every time you move, let second End The point moves two digits, the first node moves one while (second != null && second.next != null) { first = first.next; second = second.next.next; } // Until the second node moves to null At this time, the position pointed to by the first pointer is the position of the intermediate node return first; }In the above code, when n is an even number, the obtained intermediate node is n/2 + 1 node. For example, when there are 6 nodes in the linked list, the fourth node is obtained.
5. Merge two ordered single-linked lists, and the combined linked lists are still in order:
This question is often investigated by various companies.
For example:
List 1:
1->2->3->4
List 2:
2->3->4->5
After merge:
1->2->2->3->3->4->4->5
Solution idea:
Compare linked list 1 and linked list 2 next to each other.
This is similar to merge sorting. Pay special attention to the situation where both linked lists are empty and one of them is empty. Only O (1) space is required. Time complexity is O (max(len1,len2))
Code implementation:
//The two parameters represent the header nodes of the two linked lists public Node mergeLinkList(Node head1, Node head2) { if (head1 == null && head2 == null) { //If both linked lists are empty return null ; } if (head1 == null) { return head2; } if (head2 == null) { return head1; } Node head; //The head node of the new linked list Node current; //The current node points to the new linked list// At the beginning, we let the current node point to the smaller data in head1 and head2, and get the head node if (head1.data < head2.data) { head = head1; current = head1; head1 = head1.next; } else { head = head2; current = head2; head2 = head2.next; } while (head1 != null && head2 != null) { if (head1.data < head2.data) { current.next = he ad1; //In the new linked list , the next node of the current pointer corresponds to the smaller data current = current.next; // the current pointer moves head1 = head1.next; } else { current.next = head2; current = current.next; h ead2 = head2 .next; } } //Merge the remaining elements if (head1 != null) { //Indicate that the linked list 2 has been traversed and is empty. current.next = head1; } if (head2 != null) { //Indicate that the linked list 1 After traversing, it is empty.next = head2; } return head; }Code Test:
public static void main(String[] args) { LinkList list1 = new LinkList(); LinkList list2 = new LinkList(); //Add data to LinkList for (int i = 0; i < 4; i++) { list1 . add(i); } for (int i = 3; i < 8; i++) { list2.add(i); } LinkList list3 = new LinkList(); list3.head = list3.mergeLinkList(list1.head, list2. head); //Merge list1 and list2 and store it in list3 list3.print(list3.head); // Start traversing the output from the head node}The add method and print method used in the above code are consistent with the subsection 1.
Running effect:
Note: The solution is recursive in "Sword-pointing Offer", which feels a bit difficult to understand.
6. Inversion of single-linked list: [The highest frequency of occurrence]
For example, linked list:
1->2->3->4
After the inversion:
4->2->2->1
Idea:
Iterate through the original linked list from beginning to end, and each node is traversed, and it is removed and placed at the front end of the new linked list. Note that the linked list is empty and there is only one node. Time complexity is O(n)
Method 1: (traversal)
//Method: Reversal of linked list public Node reverseList(Node head) { //If the linked list is empty or there is only one node, no inversion is required, and the head node of the original linked list is directly returned to the original linked list if (head == null || head.next == null) { return head; } Node current = head; Node next = null; //Define the next node of the current node Node reverseHead = null; //The header of the new linked list after inversion (current != null) { next = current.next; //Temporarily save the next node of the current node, because you will use current.next = reverseHead next time; //Point the next node of current to the header node of the new linked list reverseHead = current; current = next; // After the operation is completed, the current node is moved backward} return reverseHead; }In the above code, the core code is lines 16 and 17.
Method 2: (Recursion)
This method is a bit difficult, so I won't talk about it for now.
7. Print a single linked list from end to end:
For this kind of inverted order, we should think of stack, first in and first out. Therefore, this question either uses the stack yourself or lets the system use the stack, that is, recursive. Pay attention to the case where the linked list is empty. Time complexity is O(n)
Note: Don’t think about reversing the single linked list first and then traversing the output. This will destroy the structure of the linked list, which is not recommended.
Method 1: (Create a new stack by yourself)
//Method: Print a single linked list from the end to the end public void reversePrint(Node head) { if (head == null) { return; } Stack<Node> stack = new Stack<Node>(); //Create a new stack Node cur rent = head; //Press all nodes of the linked list while (current != null) {- stack.push(current); //Press the current node to stack current = current.next; } //Press the stack The node prints out while (stack.size() > 0) { System.out.println(stack.pop().data); //Stack operation} }Method 2: (Use the system's stack: recursive, elegant and concise code)
public void reversePrint(Node head) { if (head == null) { return; } reversePrint(head.next); System.out.println(head.data); }Summary: Method 2 is based on recursion implementation. Diane looks concise and elegant, but there is a problem: when the linked list is very long, it will cause the method call to be very deep, which may cause stack overflow. The explicit stack of Method 1 is implemented based on loops, and the code is more robust.
8. Determine whether a single linked list has a ring:
Two pointers are also used here. If a linked list has a ring, then using a pointer to traverse will never end.
Therefore, we use two pointers to traverse: the first pointer takes one step at a time, and the second pointer takes two steps at a time. If the first pointer and the second pointer meet, it means there is a ring. The time complexity is O (n).
method:
//Method: Determine whether a single linked list has a ring public boolean hasCycle(Node head) { if (head == null) { return false; } Node first = head; Node second = head; while (second != nul l) { first = first.next; //First pointer takes one step second = second.next.next; second pointer takes two steps if (first == second) { //Once two pointers meet, it means that the linked list has a ring return true; } } return false; }Full version code: (including test part)
Here, we also need to add an overloaded add(Node node) method, which should be used when creating a one-way circular linked list.
LinkList.java: public class LinkList { public Node head; public Node current; //Method: Add data to the linked list public void add(int data) { //When judging that the linked list is empty if (head == nu ll) {/ /If the header node is empty, it means that the linked list has not been created yet, then assign the new node to the header node head = new Node(data); current = head; } else { //Create a new node, Place it behind the current node (correlate the new node with the linked list) current.next = new Node(data); //Move the current index of the linked list one by one backwards current = current.next; } } //Method Overload: Add nodes to the linked list public void add(Node node) { if (node == null) { return; } if (head == null) { head = node; current = head; } else { current.n ext = node; current = current.next; } } //Method: traverse the linked list (print out the linked list. The parameters of the method indicate that traversal starts from the node public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } //Method: Detect whether a single linked list has a ring public boolean hasCycle(N ode head) { if (head == null) { return false; } Node first = head; Node second = head; while (second != null) { first = first.next; //The first pointer takes a step second = second d.next.next; //Second pointer takes two steps if (first == second) { //Once two pointers meet, it means that the linked list has a ring return true; } } return false; } class Node { //Note: The two here Member variable permissions cannot be private, because the permissions of private are only accessible to this class. int data; //Data field Node next;//Pointer field public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list = new LinkList(); // Add data to LinkList for (int i = 0; i < 4; i++) { list.add(i); } list.add(list.head); //Add the header node to the linked list, so, single There is a loop in the linked list. Note: The structure of the ring obtained at this time is the structure of Figure 1 in the following section 8. System.out.println(list.hasCycle(list.head)); } }The code that detects whether a single linked list has a ring is line 50.
Line 88: We continue to add the header node to the linked list, and the single linked list will be looped at this time. The final running effect is true.
If 88 lines of code are deleted, the single linked list has no loops at this time, and the running effect is false.
9. Take out the ring-linked list, the length of the ring:
The link list we usually encounter is the following: (Figure 1)
The length of the ring in the picture above is 4.
But it is possible that the following is also the following: (Figure 2)
At this time, the length of the ring in the picture above is 3.
So how do you find the length of the ring?
Idea:
Here, we need to first use the hasCycle method in section 7 above (the method to determine whether there is a ring on the linked list). The return value of this method is boolean, but now we need to modify this method slightly to make it return the value For the node where we meet. Then, we can get the node where we meet. This node must be in the ring. We can let the corresponding pointer of this node go down until it returns to the origin, and then we can calculate the ring's The length is now.
method:
//Method: Determine whether a single linked list has a ring. The returned node is the node where it meets public Node hasCycle(Node head) { if (head == null) { return null; } Node first = head; Node second = head; while (second != null) { first = first.next; second = second.next.next; if (first == second) { //Once two pointers meet, it means that the linked list is a ring-based return first; //Return the node that meets} } return null; } //Method: There is a ring-linked list to get the length of the ring. The parameter node represents the node where it meets public int getCycleLength(Node node) { if (head == null) { return 0; } Node current = node; int length = 0; while (current != nu ll) { current = current.next; length++; if (current == node) { //When the current node reaches the origin return length; } } return length; }Full version code: (including test part)
public class LinkList { public Node head; public Node current; public int size; //Method: Add data to the linked list public void add(int data) { //Judge if (head = = null) {/ /If the header node is empty, it means that the linked list has not been created yet, then assign the new node to the header node head = new Node(data); current = head; } else { //Create a new node, Place it behind the current node (correlate the new node with the linked list) current.next = new Node(data); //Move the current index of the linked list one by one, current = current.next; //This operation After completion, the current node points to the newly added node} } //Method overload: add node to the linked list public void add(Node node) { if (node == null) { return; } if (head = = null) { head = node; current = head; } else { current.next = node; current = current.next; } } //Method: traverse the linked list (print out the linked list. The parameters of the method indicate that traversal starts from the node node public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } //Method: Determine whether a single linked list has a ring. The returned node is the node where it meets public Node hasCycle(Node head) { if (head == null) { return null; } Node first = head; Node second = head ; while (second != null) { first = first.next; second = second.next.next; if (first == second) { //Once two pointers meet, it means that the linked list is a ring-like return first; // Return the node you encounter } } return null; } //Method: There is a ring-linked list to get the length of the ring. The parameter node represents the node where it meets public int getCycleLength(Node node) { if (head == null) { return 0; } Node current = node; int length = 0; while (current != nu ll) { current = current.next; length++; if (current == node) { //When the current node reaches the origin return length; } } return length; } class Node { //Note: The permissions of the two member variables here cannot be is private, because the permissions of private are only accessible to this class. int data; //Data field Node next;//Pointer field public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list1 = new LinkList() ; Node second = null; //Cut down the second node//Add data to LinkList for (int i = 0; i < 4; i++) { list1.add(i); if (i == 1) { second = list1.current; //Cut down the second node} } list1.add(second); //Point the tail node to the second node of the linked list, so the single linked list has a ring. Note: The structure of the ring obtained during the process is the structure of Figure 2 in this section Node current = list1.hasCycle(list1.head); //Get the node that meets System.out.println("The length of the ring is" + list1.getCycleLength(current)); } }Running effect:
If the above test code of lines 104 to 122 is changed to the following: (i.e., change the structure in Figure 2 to the structure in Figure 1)
public static void main(String[] args) { LinkList list1 = new LinkList(); //Add data to LinkList for (int i = 0; i < 4; i++) { list1.add(i); } list1. add(list1.head); //Add the header node to the linked list (point the tail node to the header node), so the single linked list has a ring. Note: The structure of this ring obtained at this time is the structure of Figure 1 in this section. Node current = list1.hasCycle(list1.head); System.out.println("The length of the ring is" + list1.getCycleLength(current)); }Run results:
If you delete the 8th line in the above code, then the linked list has no loops, so the result of running is 0.
10. In the single linked list, the starting point of the extracted ring:
The link list we usually encounter is the following: (Figure 1)
The start point 1 of the ring in the picture above.
But it is possible that the following is also the following: (Figure 2)
At this time, the starting point of the ring in the above picture is 2.
Method 1:
Here we need to use the method of taking out the length of the ring in section 8 above to getCycleLength, and use this method to obtain the length of the ring. After getting the length of the ring, two pointer variables first and second need to be used. First let the second pointer go to the length step; then let the first pointer and second pointer take one step at the same time. When the two pointers meet, the knot when they meet. Point is the starting point of the ring.
Note: In order to find the starting point of the ring, we need to first obtain the length of the ring, and in order to obtain the length of the ring, we need to first determine whether there is a ring. So there are actually three methods used here.
Code implementation:
Core code for method 1:
//Method: Get the start point of the ring. The parameter length represents the length of the ring public Node getCycleStart(Node head, int cycleLength) { if (head == null) { return null; } Node first = head; Node second = head; //First Let the second pointer go to the length step for ( int i = 0; i < cycleLength; i++) { second = second.next; } //Then let the first pointer and second pointer take one step at the same time while (first != null && second != null) { first = first.next ; second = second.next; if (first == second) { //If two pointers meet, it means that this node is the starting point of the ring. return first; } } return null; }Full version code: (including test part)
public class LinkList { public Node head; public Node current; public int size; //Method: Add data to the linked list public void add(int data) { //Judge if (head = = null) {/ /If the header node is empty, it means that the linked list has not been created yet, then assign the new node to the header node head = new Node(data); current = head; } else { //Create a new node, Place it behind the current node (correlate the new node with the linked list) current.next = new Node(data); //Move the current index of the linked list one by one, current = current.next; //This operation After completion, the current node points to the newly added node} } //Method overload: add node to the linked list public void add(Node node) { if (node == null) { return; } if (head = = null) { head = node; current = head; } else { current.next = node; current = current.next; } } //Method: traverse the linked list (print out the linked list. The parameters of the method indicate that traversal starts from the node node public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } //Method: Determine whether a single linked list has a ring. The returned node is the node where it meets public Node hasCycle(Node head) { if (head == null) { return null; } Node first = head; Node second = head ; while (second != null) { first = first.next; second = second.next.next; if (first == second) { //Once two pointers meet, it means that the linked list is a ring-like return first; // Return the node you encounter } } return null; } //Method: There is a ring-linked list to get the length of the ring. The parameter node represents the node where it meets public int getCycleLength(Node node) { if (head == null) { return 0; } Node current = node; int length = 0; while (current != nu ll) { current = current.next; length++; if (current == node) { //When the current node reaches the origin, return length; } } return length; } //Method: Get the starting point of the ring. The parameter length represents the length of the ring public Node getCycleStart(Node head, int cycleLength) { if (head == null) { return null; } Node first = head; Node second = head; //First Let the second pointer go to the length step for ( int i = 0; i < cycleLength; i++) { second = second.next; } //Then let the first pointer and second pointer take one step at the same time while (first != null && second != null) { first = first.next ; second = second.next; if (first == second) { //If two pointers meet, it means that this node is the starting point of the ring. Return first; } } return null; } class Node { //Note: This The permissions of the two member variables at the time cannot be private, because the permissions of private are only accessible to this class. int data; //Data field Node next;//Pointer field public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list1 = new LinkList() ; Node second = null; //Cut down the second node//Add data to LinkList for (int i = 0; i < 4; i++) { list1.add(i); if (i == 1) { second = list1.current; //Cut down the second node} } list1.add(second); //Point the tail node to the second node of the linked list, so the single linked list has a ring. Note: The structure of the ring obtained during the time is the structure of Figure 2 in this section Node current = list1.hasCycle(list1.head); //Get the node where it meets int length = list1.getCycleLength(current); //Get The length of the ring System.out.println("The start point of the ring is" + list1.getCycleStart(list1.head, length).data); } }11. Determine the first intersection point where two single-linked lists intersect:
"The Beauty of Programming" P193, 5.3, Interview Question 37 has this question.
During the interview, many people's first reaction when encountering this question is: traverse each node in sequence on the first linked list. Whenever they traverse a node, traverse each node in sequence on the second linked list. . If there is a node on the second linked list the same as the node on the first linked list, it means that the two linked lists overlap at this node. Obviously, the time complexity of this method is O(len1 * len2).
Method 1: The idea of using stack
We can see two linked lists with common nodes and partially overlapping, the topological shape looks like a Y, but it cannot be an X-shaped one. As shown in the figure below:
As shown in the figure above, if a single linked list has a common node, then the last node (node 7) must be the same, and it starts from a certain node in the middle (node 6), and the subsequent nodes are The same.
The problem now is that in a single linked list, we can only traverse in sequence from the beginning nodes and finally reach the end node. The final tail node that reaches is first compared. Does this sound like "in first and then exit"? So we can think of using the characteristics of the stack to solve this problem: put the nodes of the two linked lists into two stacks, so that the end nodes of the two linked lists are located at the top of the two stacks. Next, let’s compare. A top of the stack until the last identical node is found.
In this way, we need to use two auxiliary stacks, the space complexity is O(len1+len2) and the time complexity is O(len1+len2). Compared with the brute force method at the beginning, time efficiency has been improved, which is equivalent to using space consumption for time efficiency.
So, is there a better way? Let’s talk about it next.
Method 2: Determine the first node where two linked lists intersect: use the fast and slow pointer, recommended (more optimal solution)
In Method 2 above, the reason we use the stack is because we want to traverse to reach the end nodes of the two linked lists at the same time. In fact, to solve this problem, we have an easier way: first iterate through the two linked lists to get their length. During the second traversal, go to the |len1-len2| step on the longer linked list, and then traverse on the two linked lists at the same time. The first identical node found is their first intersection point.
The time complexity of this idea is also O(len1+len2), but we no longer need auxiliary stacks, so we improve space efficiency. When the interviewer affirms our last idea, he can write the code manually.
Core code:
//Method: Find the first intersection point where two single-linked lists intersect public Node getFirstCommonNode(Node head1, Node head2) { if (head1 == null || head == null) { return null; } int length1 = get Length(head1 ); int length2 = getLength(head2); int lengthDif = 0; //The difference between the length of the two linked lists Node longHead; Node shortHead; //Find out the longer linked list if (length1 > length2) { longHead = head1; shortHead = head2; lengthDif = length1 - length2; } else { longHead = head2; shortHead = head1; lengthDif = length2 - length1; } //Change the pointer of the longer linked list to Go length for (int i = 0 ; i < lengthDif; i++) { longHead = longHead.next; } //Move the pointers of the two linked lists forward at the same time while (longHead != null && shortHead != null) { if (longHead == shortHead) { // The first identical node is the first node that intersects return longHead; } longHead = longHead.next; shortHead = shortHead.next; } return null; } //Method: Get the length of the single linked list public int getLeng th(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } retu rn length;The above are classic interview questions about Java linked lists. I hope they can help everyone pass the interview smoothly.