Chapter one – linked list topics
List feature
concept
What’s the difference between a heap and a stack?
Array: Stores elements consecutively in memory. Since each element occupies the same amount of memory, you can quickly access any element in the array by subscript. In general, arrays are good for finding elements rather than adding or removing them
Linked list: The elements of a linked list are not stored sequentially in memory, but are linked together by Pointers that exist in the elements. Each node has two parts: a data field to store the data elements and a pointer to store the address of the next node. If you want to access an element in a linked list, you need to start with the first element and work your way to the desired element location. But adding and deleting an element to a linked list data structure is as simple as changing the Pointers in the element.
What’s the difference between an array and a linked list?
The difference between:
- Storage location: Elements that are logically adjacent to each other in an array are physically adjacent to each other, not necessarily in a linked list.
- Storage: An array is a contiguous chunk of memory, whereas a linked list is not necessarily contiguous. In general, storing the same number of arrays takes up less memory, because linked lists also need space for their precursors and successors.
- Length variability: Lists can be scaled as needed, while arrays are defined to contain more data than the initial size of the array and overflow will occur.
- When searching by ordinal, array can be randomly accessed with time complexity of O(1), while linked list does not support random access, requiring O(n) on average.
- When searching by value, if the array is unordered, the time complexity of both array and linked list is O(n), but when the array is ordered, the time complexity can be reduced to O(logn) by half-search.
Array traversal versus linked list traversal
An array of
for(int i =0; i<=arr.length; i++){ print(arr[i]) }Copy the codeThe list
for(ListNode cur = head; cur! =null; cur = cur.next){
print(cur.val)
}
Copy the codeReverse traversal
An array of
for(int i = arr.length - 1; i > - 1; i--) { print(arr[i]) }Copy the codeThe list
for(ListNode cur = tail; cur ! =null; cur = cur.pre) {
print(cur.val)
}
Copy the code
The examination site parsing
A pointer to modify
Typical problem — list flipping
Because of the linked listrecursiveSex, in fact, we just reverse the two adjacent ones and do the same for the rest.
core idea
next = cur.next; // Save the value of the next node cur.next = pre; // next pointer pre = cur; // Move pre to cur = next; // Move cur to the next nodeCopy the codeList together
Matters needing attention
- There’s a loop, creating an infinite loop
- Dummy dummy dummy dummy dummy dummy dummy dummy dummy dummy dummy
- Don’t know how to do recursion
skills
1.dummy head
Function:
- Change the head node to an intermediate node to simplify the judgment.
- Return to the middle node of the list by breaking the link when appropriate
If we point a virtual head to the head node, the virtual head is the new head node, and the virtual head is not the node they gave us, it doesn’t participate in the operation, so no special judgment is required, that’s what the virtual head does.
sample
Lc206. Given the head node of a single linked list, please reverse the list and return the reversed listCopy the codeclass Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur! =null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
returnprev; }}Copy the code
2. Fast and slow pointer
Typical topics: Finding the KTH node from the tail, finding the ring entrance, finding the common tail entrance, etc
Algorithm flow: Set two-pointer FAST, slow points to the head of the linked list, fast takes 2 steps in each round, slow takes 1 step in each round;
-
The first result: the fast pointer passes through the end of the linked list, indicating that the list is loopless, and directly returns NULL;
TIPS: If there is a ring, the two hands must meet. Because the spacing between fast and slow is +1 for every turn, fast will eventually catch up with slow;
-
Second result: when fast == slow, the two Pointers meet for the first time in the ring. Below is the analysis of the relationship between the number of steps taken by FAST and slow at this time:
Suppose there are a+ B nodes in the linked list, including a node from the head of the list to the entry of the list (excluding the entry node of the list), and B node in the ring of the list;
If the two Pointers take F and S steps respectively, then: The number of steps taken by fast is twice that of slow, that is, f = 2s; Fast goes n more rings than slow, that is, f = S + Nb; F = 2nb, s = nb,
Current situation analysis:
If you let the pointer go all the way from the head of the list and count the number of steps k, then the number of all steps to the entry of the list is: k=a+ NB. At present, the number of steps taken by the slow pointer is NB. So, we just have to find a way to stop slow a step further to get to the entrance of the ring. But we don’t know what a is. What do we do?
We’re still using the two-pointer method. We build a pointer that needs to have the following properties: this pointer and slow overlap at the entry node after taking a step forward together. So where does it take a step to get to the entry node? The answer is the list head head.
The second encounter of the two Pointers:
The position of slow pointer remains unchanged, and the fast pointer points to the head node of the linked list again. Slow and fast take one step forward in each round at the same time; F = 0, s = nb;
When the fast pointer reaches the step F = A, and the slow pointer reaches the step S = a+ NB, the two Pointers overlap and point to the linked list ring entrance at the same time. Returns the node
Complexity analysis: Time complexity O(N) Space complexity O(1) : Double Pointers use extra space of constant size.
sample
Lc142. Ring list II Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.Copy the codepublic class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while(slow ! = fast) { slow = slow.next; fast = fast.next; }returnfast; }}Copy the code
3. Merge sort — top-down and bottom-up
Merge sort is based on divide-and-conquer algorithm. The most obvious implementation is a top-down recursive implementation, which has a space complexity of O(nlogn) considering the stack space of recursive calls. If you want to achieve O(1) spatial complexity, you need to use a bottom-up implementation.
Take leetcode148 sorted linked list as an example
The top-down
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
return head;
}
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while(fast ! = tail) { slow = slow.next; fast = fast.next;if(fast ! = tail) { fast = fast.next; } } ListNode mid = slow; ListNode list1 = sortList(head, mid); ListNode list2 = sortList(mid, tail); ListNode sorted = merge(list1, list2);return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while(temp1 ! =null&& temp2 ! =null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if(temp1 ! =null) {
temp.next = temp1;
} else if(temp2 ! =null) {
temp.next = temp2;
}
returndummyHead.next; }}Copy the code
conclusion
This is the first article on algorithm and data structure that I plan to update during the fall 2021 recruitment, and it will be updated continuously. My original, plagiarism shall be prosecuted.