preface
Recently, I started to write a series of articles on algorithms. The starting point is to summarize and share the articles from the perspective of algorithms. Therefore, the reading threshold of the articles is not high. In addition, most of the solutions in this article will come with legends to abstract the process of program execution. In short, if you do not understand the code, you can see the picture 😇. Among them, compared with the common iterative solution, this paper will adhere to the principle of three elements of recursion analysis, namely return value, calling unit and termination condition.
As for the three elements, it is because recursion is a fixed mode of thinking, and every implementation of recursion is based on these three elements.
The list
First of all, let’s briefly understand what is a linked list 😎
A Linked list is a discontinuous, nonsequential storage structure on a physical storage unit whose order is determined by Pointers to each node.
Linked list operation features:
- The search time is order n.
- Insert and delete time complexity is O(1)
1. Reverse linked lists
Leetcode-cn.com/problems/re…
Title description:
Reverse a single linked list.
Example:
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL
Output: 5 – > 4 – > 2 – > 3 – > 1 – > NULL
Solution 1: Double Pointers (using deconstructed assignment)
Ideas:
Create two Pointers, prev to the first node and cur to the second, iterating over the two Pointers.
Note that if you want both Pointers to move (assign) at the same time, you need to use deconstruction assignment
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head* * /
var reverseList = function(head) {
let [cur, prev] = [head, null]
while(cur) [cur.next, prev, cur] = [prev, cur, cur.next]
return prev;
};
Copy the codeSolution 2: Double Pointers (no destruct assignment)
Ideas:
Create three Pointers, one of which, temp, acts as an intermediate assignment. Each iteration points to the next node (cur.next) from the current node (cur), and after the prev node is moved, the cur node points to Temp.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head* * /
var reverseList = function(head) {
let cur = head, prev = null;
while(cur ! = =null) {
let temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev
};
Copy the code2. Lists swap neighboring elements
Leetcode-cn.com/problems/sw…
Title description:
Given a linked list, swap adjacent nodes in pairs and return the swapped list.
Example:
Enter: head = [1,2,3,4]
Output:,1,4,3 [2]
Solution 1: iteration
Ideas:
We need four Pointers prev, start, end, and temp. Where the prev pointer points to head and the temp pointer points to prev. In each iteration, the start pointer points to temp.next (head for the first time), end points to temp.next-next (head for the first time), and finally temp moves to the second node, which is swapped, that is, start.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head* * /
var swapPairs = function(head) {
let dum = new LinkNode();
dum.next = head;
let temp = dum;
while(temp.next ! = =null&& temp.next.next ! = =null) {
let start = temp.next; // head
let end = temp.next.next; // head.next
temp.next = end;
start.next = end.next;
end.next = start;
temp = start
}
return dum.next
}
Copy the codeSolution two: recursion
Abstract model:
- Return value: swapped sub list (head node, not head, next!) .
- Call unit: Define the next node of head, next, head to the swapped sublist, next to head.
- Terminating condition: head is null or head. Next is null, head is returned when only one node is left or no node is left in the child list.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(n)
Code implementation:
/ * * *@param {ListNode} head* * /
var swapPairs = function(head) {
if (head === null || head.next === null) {
return head;
}
let next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
};
Copy the code3. Merge two ordered lists to form a new ordered list
Leetcode-cn.com/problems/he…
Title description:
Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.
Example:
Input: 1->2->4, 1->3->4
Output: 1 – > 1 – > 2 – > 3 – > 4 – > 4
Solution 1: iteration
Ideas:
Create a node dum and pointer cur. Each iteration cur.next points to the smaller of the two ordered lists and moves the list. At the end of the iteration, the unequal length of the list needs to be considered. If the unequal length is, cur.next points to the longer one (that is, the list that still exists).
Complexity analysis:
Time complexity: O(M + N)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
let dum = new ListNode();
let cur = dum;
while(l1 && l2) {
if (l1.val < l2.val) {
cur.next = l1
l1 = l1.next
} else {
cur.next = l2
l2 = l2.next
}
/ / move cur
cur = cur.next
}
// Consider unequal lengths
cur.next = l1 ? l1 : l2;
return dum.next
};
Copy the codeSolution two: divide-and-conquer algorithm + recursion
Abstract model:
- Return value: a connected, sorted sublist.
- Call unit: Define a head node dum, get the smaller of the two child lists, point DUM to it, and dum. Next points to the next child list.
- Termination condition: if L1 or L2 has no nodes, the former returns L2 and the latter l1.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(n)
Code implementation:
/ * * *@param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}* /
var mergeSubLists = function (l1, l2) {
if(! l1)return l2;
if(! l2)return l1;
let dum = new ListNode();
if (l1.val < l2.val) {
dum = l1;
dum.next = mergeSubLists(l1.next, l2);
} else {
dum = l2;
dum.next = mergeSubLists(l1, l2.next);
}
return dum;
}
var mergeTwoLists = function(l1, l2) {
if(! l1 && ! l2)return null;
let head = new ListNode();
head = mergeSubLists(l1, l2);
return head;
};
Copy the code4. Delete nodes in the linked list
Leetcode-cn.com/problems/sh…
Title description:
Given a head pointer to a one-way linked list and the value of a node to delete, define a function to delete that node.
Returns the head node of the deleted list.
Example:
Enter: head = [4,5,1,9], val = 5
Output:,1,9 [4]
Solution 1: iteration
Ideas:
Define a sentinel node dum and pointer cur. Next points to head, cur points to dum. In each iteration, determine if cur.next-val equals val, and if so, make cur.next point to cur.next-next, return Dum.next, or move cur.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head
* @param {number} val
* @return {ListNode}* /
var deleteNode = function(head, val) {
let dum = new ListNode();
dum.next = head;
let cur = dum;
while(cur) {
if (cur.next.val === val) {
cur.next = cur.next.next;
return dum.next;
}
cur = cur.next;
}
return dum.next;
};
Copy the codeSolution two: recursion
Abstract model:
- Return value: The child list after the node is deleted
- Call unit: reassign the list, i.e. Head. Next points to the deleted sublist
- Terminating condition: Val of the node equals val of the node to be deleted, return next of the node
Complexity analysis:
Time complexity: O(n)
Space complexity: O(n)
Code implementation:
/ * * *@param {ListNode} head
* @param {number} val
* @return {ListNode}* /
var deleteNode = function(head, val) {
if (head.val === val) return head.next;
head.next = deleteNode(head.next, val);
return head;
};
Copy the code5. Determine if the linked list has rings
Leetcode-cn.com/problems/li…
Title description:
Given a linked list, determine whether there are rings in the list.
Example:
Enter: head = [3,2,0,-4], pos = 1
Output: true,
Where pos represents the entrance of the ring, and -1 indicates that there is no ring
Solution 1: Set the weight
Ideas:
Define a pointer cur and set collection. For each iteration, the set is used to record the node, returning true if the node already exists in the set, otherwise continue.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(n)
Code implementation:
/ * * *@param {ListNode} head
* @return {boolean}* /
var hasCycle = function(head) {
let cur = head, set = new Set(a);while(cur) {
if (set.has(cur)) {
return true
}
set.add(cur)
cur = cur.next
}
return false
};
Copy the codeSolution two: fast and slow pointer
Ideas:
Define two Pointers fast and slow. In each iteration, fast moves two nodes and slow moves one node to determine whether FAST equals slow.
If two people (A and B) start at the same time, and A runs twice as fast as B, then A and B must meet, and for the first time they meet, A is just one lap ahead of B.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head
* @return {boolean}* /
var hasCycle = function(head) {
let fast = head, slow = head;
while(slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true}}return false
};
Copy the codeSolution 3: Json.stringify () circular reference
Ideas:
Json. stringify throws an exception when converting objects with circular references.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(n)
Json.strigify is a continuous recursive process internally, but the performance is extremely poor…
Code implementation:
/ * * *@param {ListNode} head
* @return {boolean}* /
var hasCycle = function(head) {
try {
JSON.stringify(head)
} catch(e) {
return true
}
return false
}
Copy the codeSolution 4: Manually mark whether a node is accessed
Ideas:
Unlike a Set record, it identifies whether a node has been accessed by binding an attribute flag directly to the node. That is, each iteration, determine whether the node has a flag attribute (true), if yes, return true, if not, flag is true.
In essence, it is almost the same as Set, but it changes the structure of the node and cannot be changed in theory.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head
* @return {boolean}* /
var hasCycle = function(head) {
while (head) {
if (head.flag) {
return true
}
head.flag = true
head = head.next
}
return false
}
Copy the code6. Check whether the linked list has ring II
Leetcode-cn.com/problems/li…
Title description:
Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.
This is an updated version of checking whether a list has a ring, that is, not only checking whether a list has a ring, but also finding the entry of the ring.
Example:
Enter: head = [3,2,0,-4], pos = 1
Output: Returns the linked list node with index 1
Solution 1: Set Set judgment weight
Ideas:
Define a set. At each iteration, determine if the node is present in the set, store it to the set, and move the head.
The solution to the Set problem can be very simple, because the process of moving the head, the first time to find an existing node in the Set, then must be the entry node of the ring.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(n)
Code implementation:
/ * * *@param {ListNode} head
* @return {ListNode}* /
var detectCycle = function(head) {
let set = new Set(a);while(head) {
if (set.has(head)) {
return head
}
set.add(head)
head = head.next
}
return null
};
Copy the codeSolution two: fast and slow pointer
Ideas:
Similarly, you can use fast and slow Pointers to solve this problem, but when fast and slow Pointers meet, it only means that it has a ring, because the node that meets is not necessarily the entry node of the ring!
It takes two steps to solve the problem. First, use the fast or slow pointer to determine whether there is a ring. If there is a ring, the entry node of the ring needs to be found, and this process needs to be understood by the equation:
Assuming that the distance between the head node and the entry point is A, the fast pointer has gone through x circles, and the slow pointer has gone through y circles, they meet at a node in the ring, and the distance from the entry point to it is B, and the distance from it to the entry point is C, then the corresponding distance traveled by the fast pointer and the slow pointer respectively is:
Fast pointer: S (fast) = a + x(b + C) + b Slow pointer: S (slow) = a + y(b + C) + b
Since the speed of the fast pointer is twice that of the slow pointer, s(fast) = 2s(slow), then:
a + x(b + c) + b = 2[a + y(b + c) + b]
Let’s simplify it a little bit:
(b + c)(x – 2y) = a + b
Then, it is obvious that when the fast and slow Pointers meet, the fast pointer goes n more laps than the slow pointer, assuming that n = 1, that is, x-2y = 1, so:
a = c
C is exactly the distance between the fast and slow Pointers and the entry point. Therefore, we define a pointer temp to point to the head node and move the slow pointer and temp continuously until they meet, and then we find the entry point.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head
* @return {ListNode}* /
var detectCycle = function(head) {
let fast = head, slow = head;
while(slow && fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
let temp = head;
while(temp ! == slow) { temp = temp.next; slow = slow.next; }returntemp; }}return null;
};
Copy the codeSolution 3: Manually mark whether a node has been accessed
Ideas:
I’ve already explained the idea in determining linked lists, but I won’t do it here. Ditto.
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head
* @return {boolean}* /
var hasCycle = function(head) {
while(head) {
if (head.flag) {
return head
}
head.flag = true
head = head.next
}
return null
}
Copy the code7. K unary flipped linked lists
Leetcode-cn.com/problems/re…
Title description:
You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.
Example:
List: 1 – > 2 – > 3 – > 4 – > 5
If k = 2, return 2->1->4->3->5
If k = 3, return: 3->2->1->4->5
Solution one: recursion
Ideas:
This question is divided into four steps:
-
Define a sentinel node dum and pointer prev. Next points to head and prev points to dum
-
Iterate head, first define a pointer tail to prev, and move tail continuously to determine whether the length of the current linked list is greater than or equal to K. If so, the tail pointer will point to the tail node of the child linked list formed by K node. Dummy. next returns dummy.next as there are no k nodes
-
Define the myReverse function to reverse a sublist with k-group nodes. This function takes two arguments, head and tail, and the function returns the positions of the two arguments (i.e., swapping the first node to point to). Unlike a simple reversed list, this child list is tail instead of null. So, we need to define two Pointers, prev to tail.next, then P to head, each iteration using a temporary pointer temp to p.ext, then p.ext to prev, prev to p, p to temp, The iteration exits until prev equals tail
-
After reversing the sublist, you need to connect the sublist to its original location in the list. Set temp to tail.next, prev.next to head, and tail.next to temp. Second, move the pointer, that is, prev equals tail and head equals temp
Complexity analysis:
Time complexity: O(n)
Space complexity: O(1)
Code implementation:
/ * * *@param {ListNode} head
* @param {number} k
* @return {ListNode}* /
const myReverse = (head, tail) = > {
let prev = tail.next;
let p = head;
/ / move prev
while(prev ! == tail) {let temp = p.next;
p.next = prev;
prev = p;
p = temp;
}
return [tail, head]
}
var reverseKGroup = function(head, k) {
const dum = new ListNode(0);
dum.next = head;
let prev = dum;
while(head) {
let tail = prev;
// Match group K
for(let i = 0; i < k; ++i) {
tail = tail.next
if(! tail) {returndum.next; }}let temp = tail.next;
// Reverse the k group sublist
[head, tail] = myReverse(head, tail)
// Join the child list back to the original list
prev.next = head;
tail.next = temp;
prev = tail;
head = temp;
}
return dum.next;
};
Copy the codeconclusion
To do a good job, he must sharpen his tools. As the title of the article says, I started with LeetCode from scratch, and there were a lot of things to overcome… But back to basics, as long as you keep learning, everything will fall into place. I’m going to spend a lot of time writing articles about how To Play With Algorithms. If there may be improper or wrong expression in the article, you are welcome to raise an Issue and make progress together 😊 ~
❤️ Love triple punch
Writing is not easy, please give a thumbs-up if you can, it will become my motivation to keep writing!!
I am Wu Liu, like innovation, tamping source Code, focus on Vue3 source Code, Vite source Code, front-end engineering and other technology sharing, welcome to pay attention to my wechat public number: Code Center.