In our last article, “Solving Joseph’s Ring Problem”, we mentioned linked lists. Some of you may not be familiar with the data structure of linked lists. Today, we will try to hand write a linked list class implementation. Then, let’s take a look at some of the algorithms associated with linked lists.
This article is still implemented in Java language. If you are interested in implementing other languages, please leave a message to me on the wechat official account “Ouyang Feng Studio”
There are two kinds of common linear lists: unidirectional and bidirectional. The so-called one-way linked list, that is, the linked list can only be accessed through one-way, from the previous node can be accessed to the next node, and the next node can not reverse access to the previous node. Bidirectionally linked lists do not have this limitation; they can be accessed from one node to the next, as well as from the next node to the previous node.
Singly linked list
Let’s first try to implement a one-way linked list. A complete one-way linked list data structure is shown in the following figure:
Each element in a linked list is called a linked list node, the beginning node is called a head node, and the end node is called a tail node.
In a one-way linked list, there should be at least two elements in each node: data (value) and a pointer to the next node (next).
Referring to the above figure, we first construct the node data structure:
Public class Node<E> {public E value; public Node<E> next; public Node(E value) { this.value = value; }}Copy the codeNext, we create linked list collection class, add main add, delete, change, check and other related methods:
public class LinkedList<E> {
public void add(E e) {
}
public void remove(E e) {
}
public void set(int index, E e) {
}
public E get(int index) {
}
public int size() {}}Copy the codeSince it is a one-way linked list, we only save the reference to the head node here:
Public class LinkedList<E> {private Node<E> head; Private Node<E> current; private int size; public void add(E e) { Node<E> node = new Node<>(e); // For the first time, point the head node to the elementif (null == head) {
head = node;
current = head;
} else {
current.next = node;
current = node;
}
size ++;
}
public void remove(E e) {
if (null == head) return; // If the current element happens to be a head node, empty the head nodeif (e == head.value) {
head = null;
size --;
return;
}
// 由于我们已知的信息只有头节点，我们必须通过
// 遍历找到对应的节点，这就是为什么说List的查询
// 效率比LinkedList效率高的原因
Node<E> prev = head;
Node<E> next = head.next;
while(next ! = null) {if(next.value == e) { prev.next = next.next; size --; Note that if the current node happens to be the one being removed // the value of the current node needs to point to the previous nodeif (current == next) {
current = prev;
}
break;
}
prev = next;
next = next.next;
}
}
public void set(int index, E e) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("Valid index 0 ~ " + (size - 1) + ", current: " + index);
}
Node<E> current = head;
for (int i = 0; i < size; i ++) {
if (index == i) {
current.value = e;
break;
}
current = current.next;
}
}
public E get(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("Valid index 0 ~ " + (size - 1) + ", current: " + index);
}
Node<E> current = head;
for (int i = 0; i < size; i ++) {
if (index == i) {
return current.value;
}
current = current.next;
}
return null;
}
public int size() {
returnsize; }}Copy the codeThat’s the code for a one-way list. The key is to have a mental model of the data structure of the list. You need to figure out how the nodes are connected together.
Along the same lines, let’s try to implement bidirectional linked lists.
A bidirectional list differs from a unidirectional list in that the node also needs to hold a reference to the previous node. The corresponding data model can be represented by the following graph:
As you can see in the figure above, we use the last reference to point to the previous node. At the same time, a tail node reference is added to facilitate reverse traversal.
According to the data model above, the complete code is as follows:
Public class LinkedList<E> {private Node<E> head; private Node<E> tail; private int size; public void add(E e) { Node<E> node = new Node<>(e);if (null == head) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
size ++;
}
public void remove(E e) {
if (null == head) return; // If the current element happens to be a head node, empty the head nodeif (e == head.value) {
head = null;
size --;
return;
}
Node<E> prev = head;
Node<E> next = head.next;
while(next ! = null) {if(next.value == e) { prev.next = next.next; size --; // If the current node happens to be the last node, move the last node up one bitif (next == tail) {
tail = prev;
}
break;
}
prev = next;
next = next.next;
}
}
public void set(int index, E e) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("Valid index 0 ~ " + (size - 1) + ", current: " + index);
}
Node<E> current = head;
for (int i = 0; i < size; i ++) {
if (index == i) {
current.value = e;
break;
}
current = current.next;
}
}
public E get(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("Valid index 0 ~ " + (size - 1) + ", current: " + index);
}
Node<E> current = head;
for (int i = 0; i < size; i ++) {
if (index == i) {
return current.value;
}
current = current.next;
}
return null;
}
public int size() {
returnsize; }}Copy the codeIn the above article, we wrote a one-way list and a two-way list of the code implementation. Next, let’s take a look at some of the algorithms associated with linking.
Problem 1: if there is a one-way linked list, how can I quickly obtain the 5th element from the bottom of the list
This problem can be solved using two Pointers, p1 and p2, with P2 taking five steps to point to the sixth node. The two Pointers then start in sync until P2 points to the last node and P1 points to the fifth element from the bottom.
This method can obtain the fifth element from the bottom in one loop, with the lowest time complexity. The complete code is as follows:
public void f(Node head) {
Node p1 = head;
Node p2 = head;
int i = 0;
while (i < 5) {
i ++;
p2 = p2.next;
}
while(p2 ! = null) { p1 = p1.next; p2 = p2.next; } System.out.println(p1.value); }Copy the codeQuestion two: judge that there are rings in a linked list, please give the judgment method
This problem can be solved using the classic “fast or slow pointer” solution.
The so-called “fast and slow pointer” means that two Pointers, P1 and P2, are used at the same time, and P2 is faster than P1. This creates a “fast and slow” effect, so we call it the “fast and slow pointer.” “Fast and slow pointer” plays a key role in linked list algorithm problems, often can make a lot of seemingly complex problems simplified. For example, this problem can be solved by “fast or slow pointer”.
So how do you do that? Let’s take a look.
Suppose you have a one-way linked list like the one above. There are only five elements in the list. 3, 4, and 5 form a ring.
Imagine if we use two Pointers, P1 and P2, and we start p1 and P2 at the same time, but P1 moves forward only one node at a time, and P2 moves forward two nodes at a time. Is it possible for the two to meet?
In the absence of rings, it’s obvious that you’re not going to meet, but in the presence of rings, you’re going to meet. Because when they enter a linked ring at the same time, if one hand is fast and the other is slow, they will meet when the difference in steps is exactly the size of one ring, just as the hands of a clock must meet the hands of a minute.
In this way, the complete code to determine whether the list has a ring is as follows:
public boolean hasRing(Node head) {
Node p1 = head;
Node p2 = head;
while(p2 ! = null && p2.next ! = null) { p1 = p1.next; p2 = p2.next.next;if (p1 == p2) {
return true; }}return false;
}
Copy the codeIt can be seen that the “fast and slow pointer” is indeed a very effective solution, which plays a decisive role in the solution of the above two problems. Keep this solution in mind so that the interviewer can blurt out relevant questions.
Problem three: suppose there are rings in a linked list, request the size of the ring
In problem number two, we know if there is a ring in a linked list, but how do we know the size of the ring.
The minute hand is faster than the hour hand. From the first encounter, the minute hand goes faster. Keep going, and in order to catch up with the hour hand again, the minute hand should make at least one more turn. So the distance between the minute hand and the hour hand at the second encounter is exactly the size of the ring.
Following this principle, the complete code to obtain the size of the linked list ring is as follows:
public int getRingSize(Node head) { Node p1 = head; Node p2 = head; int size = 0; int index = 0; // flag whether the first encounter has occurred int hasMeeted =false;
while(p2 ! = null && p2.next ! = null) { p1 = p1.next; p2 = p2.next.next;if (hasMeeted) {
size += 1;
}
if(p1 == p2) {// Find hasMeeted astrue// Indicates that this is the second encounter, directly out of the loopif (hasMeeted) {
break;
}
hasMeeted = true; }}return size;
}
Copy the codeQ4: there is a one-way linked list. Please print the list data from end to end
Printing a linked list from end to end is a bit like the data structure model of a stack. So, here we can use a stack to hold all the nodes in the list, pop the top element of the stack, and print it. But this not only adds a certain amount of space complexity, but also adds a certain amount of time complexity.
The problem is simply printing the values in the linked list. If we could call them in the same way as stack calls, the problem would be solved.
Recursion is exactly how a stack calls, so we can use recursion to solve this problem subtly.
Here is the complete code to reverse print the linked list data using recursive calls:
public void printReverse(Node node) {
if(node ! = null) {printReverse(node.next);
System.out.println(node.value);
} else {
return; }}Copy the codeProblem 5: there is a one-way linked list, find the middle node of the list
This question may seem familiar at first, yes, it is! It’s a little bit like problem one. In problem 1 we need to find the fifth to last node, whereas in this problem we need to find the middle node of the list.
The difficulty with this problem, however, is how to ensure that the slower pointer stays exactly where the middle node is.
In fact, this is very simple, we can still use the “fast or slow pointer” method. Just set the fast pointer to take two steps at a time and the slow pointer to take one step at a time. The complete code is as follows:
public void findMidNode(Node head) {
Node p1 = head;
Node p2 = head;
while(p2 ! = null && p2.next ! = null) { p1 = p1.next; p2 = p2.next.next; } system.out.println (p1.value); }Copy the codeProblem 6: Reverse linked lists
Example:
1->2->3->4->5->NULL
5->4->3->2->1->NULL
Copy the codeIn normal thinking, to reverse a linked list, we need to save the values of the list, then build a new list, and then join them one by one.
But in fact, the above actions can actually be synchronized, the specific idea is as follows:
1) Declare variables prev and curr to point to the previous node and the current traversal node respectively.
2) If the current node is not empty, set the temporary variable next to point to the next node of the curr.
3) Make the next node of curr point to Pre, then make pre point to curr, and then make curr point to Next.
4) Repeat the above process, judging that the current node curr is not empty.
The complete code is as follows:
public void reverseLink(Node head) {
Node prev = null;
Node curr = head;
while (null != curr) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
}
Copy the codeProblem 7: If there are rings in the linked list, find the entry node of the ring
The problem still seems to be solved by using the “fast and slow Pointers” method, but the problem is: how to make the point where the Pointers meet fall exactly at the entrance of the ring, which seems to be a problem.
Let’s continue with the figure from question 2:
In question 2, we used two Pointers, P1 and P2. P1 advances one step at a time, and P2 advances two steps at a time. If they meet, it means there is a ring in the linked list.
In the figure above, there are only 5 elements in the whole list. The entry node of the list is 3, and the node where p1 and P2 Pointers meet for the first time is 4. At this position, P2 has traveled exactly one more loop distance than P1.
This is the encounter node calculated according to the design idea in question 2. The next difficulty is to try to find a way to make the Pointers meet at the entry position exactly.
Here we assume:
1) The number of nodes between the head node and the entry node is A
2) The number of nodes from the first encounter of Pointers to the entry node is B
3) The number of nodes from the encounter location node to the entry node is X
4) The number of nodes of the ring is r
If p1 traveled a distance of s, then P2 would have traveled a distance of 2s (p2 is twice as fast as P1). Looking at the figure above, we get the following equation:
s = a + b
2s = a + b + r
Copy the codeEquation two minus equation one gets s is equal to r.
From this, we can know that at the first encounter, pointer P1 has traveled exactly one ring distance.
If you look at the figure above, you get r is equal to b plus x.
From this we get several very important formulas:
s = a + b
s = r
r = b + x
Copy the codeCombine the above three equations, remove B and S, and finally get:
x = a
Copy the codeThis tells us that the distance from the encounter node to the entry node is the same as the distance from the start node to the entry node.
So, if we return the P2 pointer to the head node after the pointer encounter, and only move forward each time. Then, when the two Pointers meet again, their node happens to be the entry node.
The above derivation may be a little convoluted, if you still can’t understand, please leave me a message on the wechat public account “Ouyang Feng Studio”.
Once you know how it works, the code is simple. Here is the complete code implementation of the above idea:
public Node getRingEntryNode(Node head) {
Node p1 = head;
Node p2 = head;
while(p2 ! = null && p2.next ! = null) { p1 = p1.next; p2 = p2.next.next;if (p1 == p2) {
break; } // after the first encounter, p2 = head; // Enter the loop again until the two meet againwhile(p1 ! = null) { p1 = p1.next; p2 = p2.next; // The two meet again and the encounter node is the entry node of the ring //if (p1 == p2) {
returnp1; }}return null;
}
Copy the codeProblem 8: There are two ordered lists. Please combine them into one list and keep the list in order
Example:
Input: 1->3->5 2->3->6 Output: 1->2->3-> 5->6Copy the codeThis problem can be handled in a circular way. First, take the first element of the two lists, put the smaller value of the first element in the header, and make the list as the target list. One by one, concatenate the list to the specified location until a list is empty. If the linked list is longer, connect the remaining elements directly to the target list.
This is a conventional way to do it, and in fact, you can do it recursively. The implementation idea is similar to the loop, but the code level is easier to understand, and less code, its complete implementation is as follows:
Public Node mergeOrderedLink(Node head1, Node head2) {// Check whether there is an empty listif (null == head1) {
return head2
} else if (null == head2) {
return head1
} else {
Node newHead = null;
if (head1.data < head2.data) {
newHead = head1;
newHead.next = mergeOrderedLink(head1.next, head2);
} else {
newHead = head2;
newHead.next = newHead.next = mergeOrderedLink(head1, head2.next);
}
returnnewHead; }}Copy the codeLast question
These are the common eight list algorithm interview questions we may encounter in the interview. Finally, I’ve prepared a final problem for you, so you can try it out first. The answer can be found in the wechat public account “Ouyang Feng Studio” reply “linked list”.
Question 9: There is A one-way linked list, and you cannot get the head node of the list. There are four consecutive nodes A, B, C and D in the linked list. If B is known, how to delete it from the linked list
To read more articles, please follow the public account “Ouyang Feng Studio”
