After reading this article, you can try to solve the following problems:
21. Merge two ordered lists (simple)
23. Merge K ascending linked lists (difficult)
141. Circular linked lists (simple)
142. Circular Linked List II (medium)
876. Intermediate nodes of linked lists (simple)
160. Intersecting linked lists (simple)
Alter table NTH; alter table NTH;medium)
Last time in the video number live, with you said that there are many clever operation of single linked list, this article summarizes the basic skills of single linked list, each skill corresponds to at least one algorithm problem:
1. Merge two ordered lists
2. Merge k ordered lists
3. Find the KTH to last node of a singly linked list
Find the midpoint of a single list
5. Determine whether a single linked list contains rings and find the starting point of rings
6. Determine whether two single-linked lists intersect and find the point of intersection
These solutions are using double pointer skills, so for single linked list related problems, the use of double Pointers is very extensive, let’s look at one by one.
Merges two ordered lists
This is the most basic list technique, which is the problem in question 21 “Merging two ordered lists” :
I will give you two ordered lists and ask you to combine them into a new ordered list. The function signature is as follows:
ListNode mergeTwoLists(ListNode l1, ListNode l2);
Copy the codeThis one is relatively easy, so let’s go straight to the solution:
ListNode l1, ListNode l2) {dummy = new ListNode(-1), p = dummy; ListNode p1 = l1, p2 = l2; while (p1 ! = null && p2 ! If (p1.val > p2.val) {p.ext = p2; p2 = p2.next; } else { p.next = p1; p1 = p1.next; } // p = p; } if (p1 ! = null) { p.next = p1; } if (p2 ! = null) { p.next = p2; } return dummy.next; }Copy the codeOur while loop compares p1 and p2 each time, joining the smaller nodes to the result list:
The logic of this algorithm is similar to “zipper zipper”, L1 and L2 are similar to the zigzag on both sides of the zipper, and pointer P is like the zipper’s cable, which merges two ordered linked lists.
The code also uses a linked list algorithm that is very common in the “dummy head node” technique, also known as dummy node. Dummy nodes are placeholders that reduce code complexity by avoiding null Pointers.
Merge k ordered linked lists
Merge K ascending linked lists
The function signature is as follows:
ListNode mergeKLists(ListNode[] lists);
Copy the codeThe logic of merging K ordered linked lists is similar to merging two ordered linked lists. The difficulty lies in how to quickly get the smallest node among K nodes and connect it to the resulting linked list.
Here we will use the priority queue (binary heap) data structure, put the linked list nodes into a minimum heap, can obtain the minimum node of k nodes at a time:
ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) return null; Dummy = new ListNode(-1); ListNode p = dummy; // PriorityQueue<ListNode> pq = new PriorityQueue<>(lists. Length, (a, b)->(a.val - b.val)); For (ListNode head: lists) {if (head! = null) pq.add(head); } while (! Pq.isempty ()) {// Get the smallest node and join it to the result list. p.next = node; if (node.next ! = null) { pq.add(node.next); } // p = p; } return dummy.next; }Copy the codeWhat is the time complexity of this algorithm, which is a common interview question?
The number of elements in the priority queue PQ is at most K, so the time complexity of a poll or add method is O(logk). All linked list nodes will be added and pQ popped, so the overall time complexity of the algorithm is O(Nlogk), where K is the number of linked lists and N is the total number of nodes in these lists.
The KTH to last node of a singly linked list
It’s easy to find the KTH node in a singly linked list from front to back. A for loop loops through the past and finds it, but how do you find the KTH node from back to front?
So you might say, if there’s n nodes in the list, and the KTH node is the positive n-k node, isn’t that also a for loop thing?
Yes, but algorithms usually just give you a ListNode whose head represents a single list, so you can’t figure out the length of the list, you have to go through the list to figure out the value of n, and then you have to go through the list to figure out the n-k node.
In other words, this solution requires going through the list twice to get to the KTH node.
So, can we just go through the list once and figure out the KTH node to the last? It can be done. If you’re asked this question in an interview, the interviewer will probably want you to give a solution that only requires going through the list once.
So this is a more subtle solution, assuming k = 2, the idea is as follows:
First, we have a pointer P1 to head, and then take k steps:
Now p1, I just have to take another n-k step, and I get to the null pointer at the end of the list, right?
At this point, use a pointer p2 to head:
If p1 and P2 go forward at the same time, p1 takes n-k steps to reach the empty pointer at the end of the list, and P2 takes n-K steps to reach the KTH node from the bottom of the list:
Thus, after traversing the list only once, the KTH node, p2, is obtained.
The code for the above logic is as follows:
ListNode findFromEnd(ListNode head, int k) {ListNode p1 = head; For (int I = 0; i < k; i++) { p1 = p1.next; } ListNode p2 = head; // p1 and p2 go n-k while (p1! = null) { p2 = p2.next; p1 = p1.next; } // p2 now points to the n-k node return p2; }Copy the codeOf course, if you use the big O notation, the time is O(N) for traversing the list once and traversing it twice, but this algorithm is more tricky.
Delete the NTH node from a linked list. Delete the NTH node from a linked list.
Let’s go straight to the solution code:
Public ListNode removeNthFromEnd(ListNode head, int n) {dummy = new ListNode(-1); dummy.next = head; ListNode x = findFromEnd(dummy, n + 1); ListNode x = findFromEnd(dummy, n + 1); // delete the next-to-last node x.ext.next; return dummy.next; } private ListNode findFromEnd(ListNode head, int k) {Copy the codeThe logic is simple. To remove the NTH to the last node, we need to get a reference to the NTH + 1 to the last node, which we implement in findFromEnd.
But notice that we’re using the virtual header technique again, just to prevent null Pointers, so if there are five nodes in the list, and they tell you to delete the fifth to the last node, which is the first node, then the logic would be to find the sixth to the last node first. But there are no more nodes in front of the first node, which will cause an error.
However, with the presence of our dummy node, this problem is avoided and the situation can be removed correctly.
The midpoint of a singly linked list
The key of the problem is that we cannot directly get the length n of a single linked list. The conventional method is to calculate n by traversing the list first and then get the n / 2 node, which is the middle node.
If you want to get the intermediate node in a single pass, you also need to be clever and use the “fast and slow pointer” technique:
We have two Pointers, slow and fast, to the list header, head.
Every time slow moves forward, fast moves forward two steps, so that when FAST gets to the end of the list, slow points to the midpoint of the list.
The code implementation of the above idea is as follows:
ListNode middleNode(ListNode head) {// Slow = head, fast = head; // Stop while (fast! = null && fast.next ! = null) {// Slow = slow. Next; fast = fast.next.next; } // return slow; }Copy the codeIt is important to note that if the list length is even, that is, if there are two midpoints, our solution returns the last node.
In addition, this code slightly modified can be directly used to judge the linked list ring algorithm.
Determines whether the linked list contains rings
It is a classic problem to determine whether a single linked list contains a ring, and the solution is also to use the fast or slow pointer:
Every time the slow pointer moves further, the fast pointer moves two steps forward.
If fast finally encounters a null pointer, there is no ring in the linked list; If fast and Slow end up meeting each other, it must be that FAST has passed slow by one lap, indicating that the linked list contains rings.
All you need to do is tweak the code to find the list midpoint:
Boolean hasCycle(ListNode head) {// Slow = head, fast = head; // Stop while (fast! = null && fast.next ! = null) {// Slow = slow. Next; fast = fast.next.next; If (slow == fast) {return true; }} // no loop return false; }Copy the codeOf course, there is an advanced version of this question: if there are rings in the list, how do you calculate the starting point of the ring?
Here is a brief description of the solution:
ListNode detectCycle(ListNode head) { ListNode fast, slow; fast = slow = head; while (fast ! = null && fast.next ! = null) { fast = fast.next.next; slow = slow.next; if (fast == slow) break; } / / if the code above similar hasCycle function (fast = = null | | fast. The next = = null) {/ / fast encountered null pointer that no ring return null; } // repoint the header slow = head; // While (slow! = fast) { fast = fast.next; slow = slow.next; } return slow; }Copy the codeAs you can see, when the fast and slow Pointers meet, let one of them point to the head node, and then let them go at the same speed. When they meet again, they will be at the node where the ring started.
We assume that when the fast and slow Pointers meet, the slow pointer takes K steps, then the fast pointer fast must take 2k steps:
Fast must take k more steps than slow. The extra K steps are actually the fast pointer going around and around in the loop, so the value of K is an “integer multiple” of the loop length.
Assuming that the distance between the encounter point and the starting point of the ring is M, then combining with the slow pointer in the figure above, the distance between the starting point of the ring and the head node is k-M, that is to say, the starting point of the ring can be reached by advancing k-m steps from the head.
Coincidentally, if you continue k-m steps from the point of encounter, you also reach the beginning of the ring. Because in combination with the fast pointer in the figure above, k steps starting from the encounter point can be turned back to the encounter point, so k-M steps must be taken to the starting point of the ring:
So, if we re-point one of the fast and slow Pointers to head, and then the two Pointers move at the same speed, k-m steps will definitely meet, and that is where the ring starts.
Whether two lists intersect
The function “intersecting linked lists” is signed as follows:
ListNode getIntersectionNode(ListNode headA, ListNode headB);
Copy the codeI’m going to give you the heads of two lists, headA and headB, that might intersect.
If it intersects, your algorithm should return the node where it intersects; If there is no intersection, null is returned.
For example, if we input two linked lists as shown below:
So our algorithm should return c1.
The straightforward idea might be to use a HashSet to record all the nodes of one list and compare them to another, but that would require extra space.
What if you didn’t use extra space and just used two Pointers?
The difficulty is that since the length of two lists may be different, the nodes between two lists cannot correspond:
If two Pointers P1 and P2 are used to advance the two linked lists respectively, they cannot reach the common node at the same time, so the intersecting node C1 cannot be obtained.
So, the key to solving this problem is to somehow get P1 and P2 to the intersection c1 at the same time.
So, we can have P1 walk through A and then B, and P2 walk through B and then A, so that the two lists are “logically” joined.
If this stitching is done, p1 and P2 can enter the common part at the same time, i.e. reach the intersection node C1 at the same time:
So, you might ask, if two lists have no intersection point, can it return NULL correctly?
If c1 is a null pointer, it will return null.
With this in mind, you can write the following code:
ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p1 = headA, p2 = headB; while (p1 ! If (p1 == null) p1 = headB; else p1 = p1.next; If (p2 == null) p2 = headA; else p2 = p2.next; } return p1; }Copy the codeSo this problem is solved, O(1) in space, O(N) in time.
These are all the tips for single linked lists, and I hope they will inspire you.
Click “read the original” to view the classification of historical articles, if my public number is helpful to you, please recommend to a friend in need ~
View more quality algorithm articles click here, hand with your brush force buckle, committed to the algorithm to speak clearly! My algorithm tutorial has received 90K star, welcome to like!