Article description
Hello, everyone. This is my third article.
Undertake the first article "add, delete and check the basis of handwritten single linked list! Add a linked list problem". As mentioned in the first article, go through the basic knowledge before brushing the algorithm problem, which is very helpful for the later algorithm problem.
In this article, according to my personal problem brushing plan, I will share three simple level algorithm problems about the linked list (but I still feel not simple)
But it doesn't matter. For the algorithm problems shared from this article, individuals will write all the code about this problem and use the form of debug to decompose each step to sort it out.
By restoring the topic scene and analyzing it in the way of debug debugging, I am more impressed.
There are three topics in this article.
1, Merge two ordered linked lists
1.1 topic analysis
When you see this problem, the first reaction is to merge the two linked lists and then sort them. Um... Don't think about it. It's absolutely violent.
Or loop two linked lists and compare them, like:
for(){
for(){
if(){}
}
}
Well, the essence of this question is that you can use recursion. Let's make a sketch and describe it briefly.
Step 1:
Compare the first node of the two linked lists
If the two nodes are equal, the L2 linked list [1] is compared with the L1 linked list [2]
be careful:
After the comparison between L1 node [1] and L2 node [1], you need to modify 1 Next pointer to point to its next node.
Step 2:
Now we have obtained the L2 linked list [1]. Who does its next point to? That is, L2 linked list [1] is compared with L1 linked list [2].
After the comparison, the next of L2 linked list [1] points to L1 linked list [2], and so on.
L2 linked list [3] is compared with L1 linked list [4].
Finally, L1 linked list [4] is compared with L2 linked list [4].
After all the comparisons are completed, the whole linked list has been sorted.
The way of recursion is to compare two nodes. When a linked list is null, it means that one of the linked lists has been traversed, so you need to stop recursion and return the comparison results.
Maybe it's just a simple drawing, which is not easy to understand. Let's analyze it in the way of code debug. Please be patient and look down.
1.2 code analysis
According to the meaning of the question, you need to create two single linked lists first. For the specific creation method, please refer to my first article "addition, deletion and query of the basis of handwritten single linked list! A linked list question is attached". Not to mention, initialize the node object first.
class ListNode {
/**
* Data domain
*/
int val;
/**
* Next node pointer
*/
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
'}';
}
}
Define the method of adding a linked list.
public ListNode add(ListNode node) {
// 1. Define auxiliary pointer
ListNode temp = nodeHead;
// 2. First, judge whether the current node is the last node
if (null == temp.next) {
// The current node is the last node
temp.next = node;
return nodeHead;
}
// 3. Loop through the node. If the next node of the current node is not empty, it indicates that there are subsequent nodes
while (null != temp.next) {
// Otherwise, move the pointer back
temp = temp.next;
}
// 4. After traversal, point the pointer of the last node to the newly added node
temp.next = node;
return nodeHead.next;
}
Then create two linked lists.
/**
* Define L1 linked list
*/
ListNode l11 = new ListNode(1);
ListNode l12 = new ListNode(2);
ListNode l13 = new ListNode(4);
MergeLinkedList l1 = new MergeLinkedList();
l1.add(l11);
l1.add(l12);
/**
* Return the newly added L1 linked list
*/
ListNode add1 = l1.add(l13);
/**
* Define L2 linked list
*/
ListNode l21 = new ListNode(1);
ListNode l22 = new ListNode(3);
ListNode l23 = new ListNode(4);
MergeLinkedList l2 = new MergeLinkedList();
l2.add(l21);
l2.add(l22);
/**
* Return L2 linked list
*/
ListNode add2 = l2.add(l23);
Let's first post the code using recursion in the above figure.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/**
* If the L1 linked list is null, the recursion is terminated
*/
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
/**
* Compare the nodes of the linked list in pairs according to the description in the figure
*/
if (l1.val <= l2.val) {
/**
* L1 The node of is smaller than that of L2. According to the figure, you need to compare the next node of L1 linked list
* l1.next It means that after comparing the node size, you need to modify the pointer to connect the whole linked list in series
*/
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
/**
* Similarly, it is the same as the previous if judgment
*/
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
1.3 debug
1.3.1 L1 linked list has been created. Similarly, L2 has been created.
1.3.2 compare the first node of two linked lists
be careful:
l1.next refers to the recursive method, that is, the L1 linked list [1] described in the above figure points to the L2 linked list [1], but who does the L2 linked list [1] point to? Start entering recursion
1.3.3 as shown in the figure above, start comparing the L2 linked list [1] with the L1 linked list [2]
1.3.4 compare L1 linked list [2] with L2 linked list [3]
1.3.5 the following operations are the same. The comparison of the last two nodes is directly shown below
Here is the comparison of the last two nodes.
At this time, the L1 linked list is traversed first. You need to terminate the recursion and return to the L2 linked list. Why return L2 linked list? Look directly at the picture.
Because the last step is to compare L1 linked list [4] and L2 linked list [4], that is, L2 linked list [4] is the last node. If L1 linked list is returned, L2 linked list [4] will be discarded. Please refer to the last one in the above diagram.
Here comes the point!!!
Here comes the point!!!
Here comes the point!!!
The L1 linked list has been traversed and started to trigger recursion to return the comparison results one by one.
Is this the last step of comparing L1 linked list [4] with L2 linked list [4]? Is it obvious, L1 Next points to L1 node [4], and L1 node is its last node [4], which is the same as the final conclusion in our diagram above.
Then go back to the next step.
[3] of L2 linked list points to [4] of L1 linked list
Similarly, it's OK to return the result of the previous recursion. Let's take a look at the final sorting result.
2, Delete duplicate elements in the sorting linked list
2.1 topic analysis
Looking at this question for the first time seems quite simple. Isn't this the first article I wrote before deleting the linked list node!
Carefully examine the question. In fact, this question is simpler, because it has been explained that it is a sort linked list, so we only need to compare the current node with the next node. If it is equal, we can directly modify the next pointer.
2.1 code analysis
The definition of linked list is the same as that in the first question above, but we need to re create a single linked list.
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(1);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(4);
ListNode l6 = new ListNode(5);
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
nodeFun.add(l4);
nodeFun.add(l5);
ListNode listNode = nodeFun.add(l6);
After the creation is complete, then look at the repeated code.
public ListNode deleteDuplicates(ListNode head) {
/**
* Define auxiliary pointer
*/
ListNode temp = head;
/**
* Judge that the current node and the next node cannot be empty, because it is necessary to compare the current node with the next node
*/
while (temp != null && temp.next != null) {
/**
* If the node values are the same
*/
if (temp.val == temp.next.val) {
/**
* Indicates that the value of the current node is the same as that of the next node, then move the pointer
*/
temp.next = temp.next.next;
} else {
/**
* The pointer must be moved, or a life and death cycle will occur
*/
temp = temp.next;
}
}
return head;
}
}
2.2 debug debugging
2.2.1 according to the initialized linked list, the first node [1] should be compared with the second node [1].
Needless to say, the two nodes are equal. The next step is to enter the if judgment, which is to modify the pointer.
At this time, the second node [1] has not been directed by next, and will be recycled by GC.
2.2.2 the next step is to compare node [1] with node [3]
If the two nodes are not equal, enter else to move the auxiliary pointer to the next node.
Then the judgment of the remaining nodes is the same. Let's finally look at the printed results.
3, Circular linked list
3.1 topic analysis
If there are links in the linked list, one of the nodes must be guided by the pointer one or more times (if there are multiple links). Therefore, the simple way for individuals at that time was to traverse the linked list, save the traversed node objects in the HashSet, and compare them in the HashSet every time they traverse the next node. If there is a ring, it means there is a ring.
This problem does not set too many requirements, as long as there is a ring to return to boolean.
There is also a clever way of writing, using the idea of fast and slow pointers.
This method roughly means that the fast and slow pointer is compared to the tortoise and rabbit race. The rabbit runs fast. If there is a ring, the rabbit will run into the ring first than the tortoise. Then they will meet on a node. If they meet, it means that the linked list has rings.
So, is your question coming? It's not fair. The rabbit runs faster than the tortoise. Why did the rabbit run first.
Imagine that if they both run on a node, they will meet from the beginning, because we set that if they meet on a node, it means that the linked list has rings. Therefore, this is not "no self Recruitment"!
At the beginning of the game, the [big brother rabbit] is a little fierce. Run two nodes at a time.
Sure enough, lovers get married and they meet.
3.2 code analysis
This time, when creating a linked list, you can't just be a single linked list. You have to add a ring.
ListNode l1 = new ListNode(3);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(0);
ListNode l4 = new ListNode(-4);
/**
* Add a ring to the protagonist
*/
l4.next = l2;
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
ListNode listNode = nodeFun.add(l4);
Let's find the ring together.
public boolean hasCycle(ListNode head) {
ListNode temp = head;
if(null == head){
// Empty means there is no ring
return false;
}
// 1. The set set saves the traversed nodes. If the new node is already in the set, it indicates that there is a ring
// 2. The idea of using fast and slow pointers
// Define slow pointer
ListNode slow = head;
// Define fast pointer
ListNode fast = head.next;
// Loop, as long as the two pointers do not coincide, it will loop all the time
while(slow != fast){
// If both pointers reach the tail node, there is no ring
if(fast == null || fast.next == null){
return false;
}
// Otherwise, move the pointer
slow = slow.next;
fast = fast.next.next;
}
return true;
}
3.3 debug debugging
So, the embarrassing thing is coming. This thing can't be debug ged. If there is a ring, the while loop will not come in.
Let's just look at the results.
If you remove the ring?
Guess? There's no aura. It must be...
4, Summary
The topics of this sharing summary are simple ones, because they are also started according to the brushing plan formulated by myself. Later, I will sort out and share my brushing plan.
About the complete code in the article, pay attention to the official account reply [get source], all the code is a project, and it is also convenient for the code update later, can debug by yourself.
Look forward to sharing with you!
Finally, ask for attention
Originality is not easy. Every article is written with heart. If it helps you, please click three times (follow, like, and then forward)
I'm Yang Xiaoxin. I insist on writing and share more meaningful articles.
Thank you for reading and look forward to meeting you!
