This series is my summary of data structure and algorithm when I was looking for a job many years ago. There are basic parts and classic interview questions of various companies. It was first published on CSDN. Is sorted out for a series of friends in need of reference, if there is a mistake, welcome to correct. The full code address for this series is here.
0 overview
As a basic data structure, linked lists are used in many places. Such as Linux kernel code, Redis source code, Python source code are used. In addition to one-way linked lists, there are also two-way linked lists. This article focuses on one-way linked lists (including some circular linked list topics, will be noted in the title, the other cases are to discuss simple one-way linked lists). Bidirectional linked lists are well implemented in Redis, and I have a copy of them in my repository for testing purposes. The code for this article is here.
1 definition
First define a one-way linked list structure, as follows, define the linked list node and linked list two structures. Here I did not define a linked list structure, save the head pointer, tail pointer, linked list length and other information, the purpose is also to practice pointer operation.
Typedef struct ListNode {struct ListNode *next; int value; } listNode;Copy the code
2 Basic Operations
On the basis of the list definition in the previous section, we complete several basic operation functions, including initialization of the list, adding nodes to the list, removing nodes from the list, etc.
/** * create a ListNode */ ListNode *listNewNode(int value) {ListNode *node;if(! (node = malloc(sizeof(ListNode))))return NULL;
node->value = value;
node->next = NULL;
returnnode; } /** * insert a header into a node. */ ListNode *listAddNodeHead(ListNode *head, int value) { ListNode *node;if(! (node = listNewNode(value)))return NULL;
if (head)
node->next = head;
head = node;
returnhead; } /** * inserts a node with value. */ ListNode *listAddNodeTail(ListNode *head, int value) { ListNode *node;if(! (node = listNewNode(value)))return NULL;
returnlistAddNodeTailWithNode(head, node); } /** * insert into nodes. */ ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node) {if(! head) { head = node; }else {
ListNode *current = head;
while (current->next) {
current = current->next;
}
current->next = node;
}
returnhead; } /** * remove the node with value from the linked list. */ ListNode *listDelNode(ListNode *head, int value) { ListNode *current=head, *prev=NULL;while (current) {
if (current->value == value) {
if (current == head)
head = head->next;
if (prev)
prev->next = current->next;
free(current);
break;
}
prev = current;
current = current->next;
}
returnhead; } /** * list traversal. */ void listTraverse(ListNode *head) { ListNode *current = head;while (current) {
printf("%d", current->value);
printf("- >");
current = current->next;
if(current == headbreak;
}
printf("NULL\n"); } /** * initializes a linked list with an array of len elements. */ ListNode *listCreate(int a[], int len) { ListNode *head = NULL; int i;for (i = 0; i < len; i++) {
if(! (head = listAddNodeTail(head, a[i])))return NULL;
}
returnhead; } /** * listLength function */ int listLength(ListNode *head) {int len = 0;while (head) {
len++;
head = head->next;
}
return len;
}
Copy the code3. Linked list related interview questions
3.1 Reverse linked list
Given a unidirectional linked list 1->2->3->NULL, the reverse order becomes 3->2->1->NULL.
Solution: The common method is to connect each node in reverse order in a circular way, as follows:
/** * list reverse order, non-recursive implementation. */ ListNode *listReverse(ListNode *head) { ListNode *newHead = NULL, *current = head;while (current) {
ListNode *next = current->next;
current->next = newHead;
newHead = current;
current = next;
}
return newHead;
}
Copy the codeIf it’s a bit of a show-off, let’s do a recursive solution like this:
/** * list in reverse order, recursive implementation. */ ListNode *listReverseRecursive(ListNode *head) {if(! head || ! head->next) {return head;
}
ListNode *reversedHead = listReverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return reversedHead;
}
Copy the code3.2 Linked list Replication
Given a one-way linked list, copy and return the new list header.
Solution: There are also two possible solutions, non-recursive and recursive, as follows:
/** * ListNode *listCopy(ListNode *head) {ListNode *current = head, *newHead = NULL, *newTail = NULL;while (current) {
ListNode *node = listNewNode(current->value);
if(! NewHead = newTail = node; }else {
newTail->next = node;
newTail = node;
}
current = current->next;
}
returnnewHead; } /** *list copy - recursive */ ListNode *listCopyRecursive(ListNode *head) {if(! head)return NULL;
ListNode *newHead = listNewNode(head->value);
newHead->next = listCopyRecursive(head->next);
return newHead;
}
Copy the code3.3 Linked list merging
Given two ordered unidirectional lists, please merge the two lists so that the combined lists are still ordered (note: the two lists have no common nodes, i.e. do not cross). Such as chain table 1 is 1 – > 3 – > 4 – > NULL, chain table 2 is 5-2 – > > 6-7-8 – > > > NULL, then the combined list for 1 – > 2 – > 3 – > 4 – > 5 – > 6-7-8 – > > > NULL.
Solution: This is very similar to the last step of merge sort, just merge two ordered lists together. Two Pointers are used to traverse the two linked lists separately, and the smaller value nodes are merged into the resulting linked list. If a list is merged and another list has nodes, the rest of the other list is added to the end of the resulting list. The code looks like this:
/** *listMerge - non-recursive */ ListNode *listMerge(ListNode *list1, ListNode *list2) {ListNode dummy; ListNode *tail = &dummy; ListNode *tail = &dummy;if(! list1)return list2;
if(! list2)return list1;
while (list1 && list2) {
if (list1->value <= list2->value) {
tail->next = list1;
tail = list1;
list1 = list1->next;
} else{ tail->next = list2; tail = list2; list2 = list2->next; }}if (list1) {
tail->next = list1;
} else if (list2) {
tail->next = list2;
}
return dummy.next;
}
Copy the codeOf course, to implement a recursion is not difficult, the code is as follows:
ListNode *listMergeRecursive(ListNode *list1, ListNode *list2)
{
ListNode *result = NULL;
if(! list1)return list2;
if(! list2)return list1;
if (list1->value <= list2->value) {
result = list1;
result->next = listMergeRecursive(list1->next, list2);
} else {
result = list2;
result->next = listMergeRecursive(list1, list2->next);
}
return result;
}
Copy the code3.4 Link list intersection judgment
Given two unidirectional lists list1 and list2, determine whether the two lists intersect. If it intersects, find out where it intersects.
Solution 1: It is possible to directly traverse list1 and then determine whether each node of List1 is in List2, but the complexity of this solution is O(length(list1) * length(list2)). Length (length(list1) + length(list2))); space (length(list1)); space (length(list1)); So we can figure out where we’re going to intersect. Of course, there are better ways to find intersecting nodes.
Solution 2: If two lists intersect, their nodes from the intersection must be the same. If the length of list1 is len1, the length of List2 is len2, and len1 > len2, then we only need to traverse len1 through len1-LEN2 nodes first, and then the two nodes together. If the node is equal, the node will be the first intersection node.
/** * if the list intersects, return the intersecting node, otherwise return NULL. */ ListNode *listIntersect(ListNode *list1, ListNode *list2) { int len1 = listLength(list1); int len2 = listLength(list2); int delta = abs(len1 - len2); ListNode *longList = list1, *shortList = list2;if (len1 < len2) {
longList = list2;
shortList = list1;
}
int i;
for (i = 0; i < delta; i++) {
longList = longList->next;
}
while (longList && shortList) {
if (longList == shortList)
return longList;
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
Copy the code3.5 Determine whether the linked list has rings
Given a linked list, determine whether there are rings in the list.
Solution 1: The easy way to think about it is to use a hash table to record the nodes that have appeared and walk through the linked list. If a node appears repeatedly, it indicates that the linked list has a ring. If the hash table is not used, a visited field can also be added to the ListNode structure of the linked ListNode to mark it, and the visited field marked as 1 can also be detected. Since we haven’t implemented a hash table yet, this method code will be added later.
Solution 2: A better method is the Floyd loop detection algorithm, which was first developed by Robert. Freud invented it. The linked list is traversed by using two Pointers fast and slow, the fast pointer taking two steps at a time and the slow pointer taking one step at a time. If fast and slow meet, then there is a ring, otherwise there is no ring. (Note that if the list has only one node and no loop, it does not enter the while loop)
Detectloop (ListNode *head) {ListNode *slow, *fast; ListNode *head (ListNode *head) {ListNode *slow, *fast; slow = fast = head;while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
printf("Found Loop\n");
returnslow; }}printf("No Loop\n");
return NULL;
}
void testListDetectLoop()
{
printf("\nTestListDetectLoop\n"); int a[] = {1, 2, 3, 4}; ListNode *head = listCreate(a, ALEN(a)); listDetectLoop(head); Head ->next->next->next = head; listDetectLoop(head); }Copy the codeExtension: how to find the entry point of a linked list ring if a ring is detected?
First, let’s prove why the algorithm mentioned in solution 2 above is correct. If the list does not have a loop, because the fast pointer takes 2 steps each time, it must reach the end of the list before the slow pointer, and will not meet.
If there is a ring, it is assumed that the fast and slow Pointers meet after s cycles, then the distance traveled by the fast Pointers is 2s, and the distance traveled by the slow Pointers is S. Assuming that the number of nodes in the ring is R, the following conditions must be met in order to meet, that is, the number of encounters meets s = nr. That is, the next encounter from the starting point requires r cycles.
2s - s = nr => s = nr
Copy the codeAs shown in the figure below, ring length r=4, then the next encounter from the starting point needs to go through 4 cycles.
So how do we find the entry point of the ring? It can be seen from the previous that r times are required for the first encounter, and the distance traveled by the slow pointer is S = R. Set the total length of the linked list as L, the distance from the head of the list to the ring entrance as A, and the distance from the ring entrance to the encounter point as X, then L = a + R, and a = (L-x-a) can be deduced. Wherein, L-x-a is the distance from the encounter point to the ring entrance point, that is, the distance a from the list head to the ring entrance is equal to the distance from the encounter point to the ring entrance.
s = r = a + x => a + x = (L-a) => a = L-x-a
Copy the codeTherefore, after judging the existence of a ring in the linked list, the traversal starts from the encounter point and the head node respectively, and the two Pointers take a step each time. When the two Pointers are equal, it is the entry point of the ring.
/** *findLoopNode(ListNode *head) {ListNode *meetNode = listDetectLoop(head);if(! meetNode)return NULL;
ListNode *headNode = head;
while(meetNode ! = headNode) { meetNode = meetNode->next; headNode = headNode->next; }return meetNode;
}
Copy the code3.6 Linked lists simulate addition
Given two linked lists, the node value of each list is the digit on the digit digit, try to find the sum of the digits represented by the two linked lists, and return the result as a linked list. Suppose the two linked lists are respectively list1 and list2. The values of each node of List1 are the ones, tens, and hundreds digits of the number 513, and the values of each node of List2 are the digits of the number 295. The two numbers add up to 808, so the output is printed in order from the ones to the hundreds, and the linked list of results is returned as follows.
List1: (3 -> 1 -> 5 -> NULL) List2: (5 -> 9 -> 2 -> NULL) result: (8 -> 0 -> 8 -> NULL)Copy the codeSolution: This topic is interesting, need to be familiar with linked list operation. We consider the process of adding two digits from the lowest digit to the highest digit, marking the carry flag if there is a carry, and terminating until the highest digit. Set the node of the current bit to current, then:
Current ->data = list1->data + list2->data + carry (where carry is 1, otherwise 0)Copy the codeThe non-recursive code is as follows:
/** *listEnumarateAdd(ListNode *list1, ListNode *list2) {int carry = 0; ListNode *result = NULL;while (list1 || list2 || carry) {
int value = carry;
if (list1) {
value += list1->value;
list1 = list1->next;
}
if(list2) { value += list2->value; list2 = list2->next; } result = listAddNodeTail(result, value % 10); carry = ( value >= 10 ? 1:0); }return result;
}
Copy the codeThe non-recursive implementation is as follows:
/ * * * list analog addition - * / ListNode * listEnumarateAddRecursive recursive method (ListNode * list1, ListNode * list2, int carry) {if(! list1 && ! list2 && carry==0)return NULL;
int value = carry;
if (list1)
value += list1->value;
if(list2) value += list2->value; ListNode *next1 = list1 ? list1->next : NULL; ListNode *next2 = list2 ? list2->next : NULL; ListNode *more = listEnumarateAddRecursive(next1, next2, (value >= 10 ? 1:0)); ListNode *result = listNewNode(carry); result->value = value % 10; result->next = more;return result;
}
Copy the code3.7 Ordered unidirectional circular linked lists are inserted into nodes
Given an ordered one-way circular linked list, insert a node and keep the list ordered, as shown below.
Solution: Before we solve this problem, let’s look at the simplified version, which is to insert nodes into an ordered, non-cyclic, one-way linked list, and still keep the order. The code of this question is believed to be familiar to most people, generally divided into two cases to consider:
- 1) If the original linked list is empty or the inserted node has a minimum value, the node is directly inserted and set as the head node.
- 2) If the original linked list is not empty, find the first node whose value is greater than the value of the node and insert it in front of the node. If the inserted node has the largest value, it is inserted at the end.
The implementation code is as follows:
*/ ListNode *sortedListAddNode(ListNode *head, int value) {ListNode *node = listNewNode(value);if(! Head | | head - > value > = value) {/ / situation 1 node - > next = head; head = node; }elseListNode *current = head;while(current->next ! = NULL && current->next->value < value) current = current->next; node->next = current->next; current->next = node; }return head;
}
Copy the codeOf course, both cases can be handled together, using second-level Pointers. As follows:
Void sortedlistaddnodehead (ListNode, ListNode, ListNode, ListNode, ListNode) int value) { ListNode *node = listNewNode(value); ListNode **current = head;while ((*current) && (*current)->value < value) {
current = &((*current)->next);
}
node->next = *current;
*current = node;
}
Copy the codeIn the case of circular lists, there are two things to consider:
- 1) prev->value ≤ value ≤ current->value: insert between prev and current.
- 2) Value is the maximum or minimum value: insert to the intersection of head and tail, if it is the minimum value reset head value.
The code is as follows:
*/ ListNode *sortedLoopListAddNode(ListNode *head, int value) {ListNode *node = listNewNode(value); ListNode *current = head, *prev = NULL;do {
prev = current;
current = current->next;
if (value >= prev->value && value <= current->value)
break;
} while(current ! = head); prev->next = node; node->next = current;if(current == head && value < current->value)return head;
}
Copy the code3.8 Output the penultimate KTH node of the linked list
Given a simple one-way linked list, output the KTH node to the end of the list.
Solution 1: If it’s the KTH node, you don’t have to think about it. What’s new about this problem is that it’s going to output the penultimate KTH node. An intuitive way to think about it is, given a list of length L, the KTH node to the end is L minus K plus 1. If the length of the list is 3, the second-to-last node is the second node of the sequence. You need to walk through the list twice, once to find the length and once to find the node.
*/ ListNode *getLastKthNodeTwice(ListNode *head, int K) {int len = listLength(head);if (k > len)
return NULL;
ListNode *current = head;
int i;
for(i = 0; i < len-k; Current = current->next;return current;
}
Copy the codeSolution 2: Of course, a better way is to iterate once, set two Pointers p1,p2, first p1 and p2 both point to head, and then P2 takes k steps forward, so that there are k nodes between p1 and P2. And then p1 and P2 move forward at the same time, and p2 goes to the end of the list and P1 points to the KTH node. The code is as follows:
*/ ListNode *getLastKthNodeOnce(ListNode *head, int K) {ListNode *p1, *p2; p1 = p2 = head;for(; k > 0; k--) {
if(! P2) // The list length is insufficient Kreturn NULL;
p2 = p2->next;
}
while (p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
Copy the codeThe resources
- www.geeksforgeeks.org/detect-loop…
- www.cppblog.com/humanchao/a…
- www.geeksforgeeks.org/find-first-…
- www.geeksforgeeks.org/merge-two-s…