1 the introduction
The operation algorithm of single – linked list is a common topic in written interview. This article will focus on the common interview questions about linked lists, hope you can help
2 Outputs the penultimate KTH node of the single-linked list
2.1 Problem Description
Title: Input a single linked list and output the KTH to last node in the list. (Node count starts at 1 after removing the head node)
2.2 Double pass
2.2.1 Idea of problem solving
(1) Traverse the single linked list, and obtain the length of the list N at the same time. (2) Repeat from the beginning, and access to the n-k node as the desired node.
2.2.2 Illustrated process
2.2.3 Code implementation
/* Calculate the list length */
int listLength(ListNode* pHead){
int count = 0;
ListNode* pCur = pHead->next;
if(pCur == NULL) {printf("error");
}
while(pCur){
count++;
pCur = pCur->pNext;
}
return count;
}
/* Find the value of the KTH node */
ListNode* searchNodeK(ListNode* pHead, int k){
int i = 0;
ListNode* pCur = pHead;
// Calculate the list length
int len = listLength(pHead);
if(k > len){
printf("error");
}
// loop len-k+1 times
for(i=0; i < len-k+1; i++){
pCur = pCur->next;
}
return pCur;// Returns the penultimate KTH node
}
Copy the codeIn this way, the list is traversed twice, and the time complexity is O(n*2). So this is the simplest and easier to understand, but it’s inefficient.
2.3 the recursive method
2.3.1 Idea of problem solving
(1) Define num = k (2) recursively traverse to the end of the list. (4) When num is 0, the target node can be found
2.3.2 Illustrated process
2.3.3 Code implementation
int num;// Define the num value
ListNode* findKthTail(ListNode* pHead, int k) {
num = k;
if(pHead == NULL)
return NULL;
// recursive call
ListNode* pCur = findKthTail(pHead->next, k);
if(pCur ! =NULL)
return pCur;
else{
num--;// Return recursively, num is reduced by 1
if(num == 0)
return pHead;// Returns the penultimate KTH node
return NULL; }}Copy the codeSo if you do it recursively, you still need to go through the list twice in order n times 2.
2.4 Two-pointer method
2.4.1 Idea of problem solving
(1) Define two Pointers P1 and P2 to point to the head node of the linked list respectively. (2) IF P1 advances K nodes, the distance between P1 and P2 is K nodes. (3) P1 and P2 advance at the same time, advancing 1 node each time. (4) When P1 points to the end of the linked list, since P1 and P2 are K nodes apart, p2 points to the target node.
2.4.2 Diagram the process
2.4.3 Code implementation
ListNode* findKthTail(ListNode *pHead, int K){
if (NULL == pHead || K == 0)
return NULL;
// both p1 and p2 point to the head node
ListNode *p1 = pHead;
ListNode *p2 = pHead;
//p1 starts first and advances K nodes
for (int i = 0; i < K; i++) {
if (p1)// Prevent k from exceeding the number of linked list nodes
p1 = p1->_next;
else
return NULL;
}
while (p1)// If p1 does not reach the end of the list, p1, p2 continue traversing
{
p1 = p1->_next;
p2 = p2->_next;
}
return p2;// When p1 reaches the end, P2 points to the KTH node from the bottom
}
Copy the codeAnd you can see that using the two-pointer method you only have to go through the list once, which is more efficient and O(n) time, and that’s usually what you’re going to do on a written question.
3 There are ring problems in linked lists
3.1 Determine whether the linked list has rings
A ring in a single linked list means that the next pointer of the node at the end of the list is not NULL, but points to a node in the list, resulting in a ring structure in the list.
The linked list has a ring schematic:
The last node of the list, 8, points to node 3 in the list, resulting in a ring structure in the list. What are the ways to tell if a list is looped or not?
3.1.1 Exhaustive comparison method
3.1.1.1 Problem solving ideas
(1) Traverse the linked list and record the nodes that have been visited. (2) Compare the current node with previous and visited nodes. If there are same nodes, there is a ring. Otherwise, there is no ring.
This exhaustive comparison is simple in idea, but inefficient, especially when there are a large number of linked list nodes, it takes a lot of time to compare, and the time complexity is roughly O(n^2). This method is not, of course, the ideal answer of the questionmaker. If you use this method in a written interview, you’ll probably be on your knees. Forget it.
3.1.2 Hash caching
Since the comparison process takes a lot of time in exhaustive traversal, what can be done to speed up the comparison?
3.1.2.1 Problem solving ideas
(1) First create a HashSe T set with node ID as the key to store the nodes that have been traversed. (2) Starting from the beginning node, traverse each node of the single linked list in turn. (3) Every time a new node is traversed, the new node is compared with the nodes stored in the HashSet. If the same node ID is found in the HashSet, it indicates that the linked list has a ring. If the same node ID does not exist in the HashSet, Store the new node ID into the HashSet, and then go to the next node and repeat.
Suppose the distance from the head of the list to the entry point is A and the ring length of the list is R. The time complexity of each HashSet element lookup is O(1), so the overall time complexity is 1 * (a + R) = a + R, which can be simply understood as O(n). The spatial complexity of the algorithm is still a + R-1, which can be simply understood as O(n).
3.1.3 Fast and slow pointer method
3.1.3.1 Problem solving ideas
(1) Define two Pointers as slow and fast respectively, and point to the head node of the linked list. (2) It is stipulated that the slow pointer advances one node at a time, and the fast pointer advances two nodes at a time. (3) When slow and fast are equal, and neither of them is empty, the linked list has a ring.
3.1.3.2 Diagram the process
Acyclic process:
As can be seen from the diagram, if there is no ring in the table, the fast and slow Pointers can only meet at the end of the linked list.
Looped process:
As can be seen from the diagram, if there are rings in the linked list, the fast and slow hands must meet in the rings. It’s like running the tortoise and the hare on a circular track. As the speed of the rabbit is greater than the speed of the tortoise, it is inevitable that the rabbit and the tortoise meet again. Therefore, when fast and slow Pointers are equal, and both are not NULL, it indicates that the linked list has a ring.
3.1.3.3 Code implementation
bool isExistLoop(ListNode* pHead) {
ListNode* fast;// Slow pointer, one node at a time
ListNode* slow;// Fast pointer, 2 nodes at a time
slow = fast = pHead ; // Both Pointers point to the head of the list
// If you do not reach the end of the list, proceed
while(slow ! =NULL&& fast -> next ! =NULL) {
slow = slow -> next ; // Slow the pointer forward one node
fast = fast -> next -> next ; // Fast pointer forward two nodes
if (slow == fast) // If two Pointers meet and neither is NULL, a ring exists
return true ;
}
// If the end is still not met, there is no ring
return false ;
}
Copy the code3.2 Locating the ring entrance
In section 3.1, the method to determine whether there is a ring in a linked list has been implemented. So, when there are rings in the linked list, how do you determine the entry node of the ring?
3.2.1 Idea of problem solving
The slow pointer moves forward one node at a time, so when slow meets fast, slow has not traversed the entire linked list. Set s for slow and 2s for fast. Set the distance from the entry point of the ring to the head node as A, the distance from the first encounter point of slow and fast to the entry point as B, and the length of the ring as R. S = a + b; 2s = n * r + a + b; N represents the number of turns that the fast pointer has already looped through the loop. S = n * r; Means that the slow pointer travels an integer multiple of the length of the ring.
If the degree between the head node of the list and the end node of the ring is L, the distance between the meeting node of slow and fast and the entry node of the ring is X. A +X = s = n * r = (n-1) * r + (L – a); a = (n – 1) * r + (L – a – X); As can be seen from the above equation, starting from the meeting point of Slow and fast, a pointer P1 moves forward (L-A-x), then the pointer reaches the entry node. At the same time, p2 starts at the beginning and advances a step. When P1 meets P2, both P1 and P2 point to the entry node.
For example, the linked list shown in Figure 3.1: slow walking node s = 6; Fast passes through the node 2s = 12; Loop inlet node data flow head node A = 3; The distance between the encounter point and the head node X = 3; L = 8; R = 6; So a is equal to n minus 1 times r plus L minus a minus X.
3.2.2 Illustrated process
3.2.3 Code implementation
// Find the encounter node in the ring
ListNode* getMeetingNode(ListNode* pHead) // Assume a singly linked list of leading nodes
{
ListNode* fast;// Slow pointer, one node at a time
ListNode* slow;// Fast pointer, 2 nodes at a time
slow = fast = pHead ; // Both Pointers point to the head of the list
// If you do not reach the end of the list, proceed
while(slow ! =NULL&& fast -> next ! =NULL){
slow = slow -> next ; // Slow the pointer forward one node
fast = fast -> next -> next ; // Fast pointer forward two nodes
if (slow == fast) // If two Pointers meet and neither is NULL, a ring exists
return slow;
}
// If the end is still not met, there is no ring
return NULL ;
}
// Find the entry node of the ring
ListNode* getEntryNodeOfLoop(ListNode* pHead){
ListNode* meetingNode = getMeetingNode(pHead); // Find the encounter node in the ring
if (meetingNode == NULL)
return NULL;
ListNode* p1 = meetingNode;
ListNode* p2 = pHead;
while(p1 ! = p2)// P1 and P2 move forward at the same speed. By the time P2 points to the entry node of the ring, P1 has gone n times around the ring and returned to the entry node.
{
p1 = p1->next;
p2 = p2->next;
}
// return to the entry node
return p1;
}
Copy the code3.3 Calculating ring length
3.3.1 Idea of problem solving
In 3.1, the meeting node of slow and FAST is found, so that solw and FAST Pointers start from the meeting node. According to the previous advance rules, when slow and FAST meet again, the length of slow traversing is exactly the length of the ring.
3.3.2 Illustrated process
3.3.3 Code implementation
int getLoopLength(ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
while ( fast && fast->next ){
slow = slow->next;
fast = fast->next->next;
if ( slow == fast )// First encounter
break;
}
// Slow and fast continue
slow = slow->next;
fast = fast->next->next;
int length = 1; / / loop length
while( fast ! = slow )// Meet again
{
slow = slow->next;
fast = fast->next->next;
length ++; / / accumulation
}
// When slow and fast meet again, the loop length is obtained
return length;
}
Copy the codeUse linked lists to add large numbers
4.1 Problem Description
Two integers represented by a linked list, where each node contains a number. The numbers are stored in the reverse order of the original integers, such that the first number is at the beginning of the list. Write a function that adds two integers and returns the sum as a linked list.
For example: input: 3 – > 1 – > 5 – > null – > 9 – > 2 – > null, output: 8 – > 0 to 8 – > > null
4.2 Code Implementation
ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
ListNode *ret = l1, *pre = l1;
int up = 0;
while(l1 ! =NULL&& l2 ! =NULL) {
// Add values
l1->val = l1->val + l2->val + up;
// Calculate whether there is a carry
up = l1->val / 10;
// Keep the ones bits of the result
l1->val %= 10;
// Record the current node location
pre = l1;
// Simultaneously shift backwards
l1 = l1->next;
l2 = l2->next;
}
// If l1 reaches the end, l1 is less than L2
if (l1 == NULL)
//pre->next points to the current position of L2
pre->next = l2;
//l1 points to the current position of L2
l1 = pre->next;
// Continue counting the remaining nodes
while(l1 ! =NULL) {
l1->val = l1->val + up;
up = l1->val / 10;
l1->val %= 10;
pre = l1;
l1 = l1->next;
}
// If the highest bit is carried, create a new node to retain the highest bit
if(up ! =0) {
ListNode *tmp = new ListNode(up);
pre->next = tmp;
}
// Returns a list of calculated results
return ret;
}
Copy the code5 Ordered list merge
5.1 Problem Description
Title: Merge two ordered lists into a new ordered list and return. A new list is formed by concatenating all the nodes of a given two lists.
Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
5.2 Algorithm Flow
5.3 General Scheme
5.3.1 Idea of problem solving
(1) Handle the existence of an empty linked list. If pHead1 is empty, pHead2 is returned, and pHead1 is returned if pHead2 is empty. (2) Determine the first node in the case of two linked lists without empty lists, compare the value of the first node of linked list 1 and linked list 2, and save the node with the lower value as the first node after merging. And move the first node back one element from the smallest list. (3) Continue to select small values from the remaining elements and connect them to the end of the first node, and continue to next to connect nodes with small values to the end of the first node until a linked list is empty. (4) When the length of two linked lists is inconsistent, that is, after the comparison is completed, one of the linked lists is empty. In this case, the remaining elements of the other linked list need to be connected to the end of the first node.
5.3.2 Code implementation
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* pTail = NULL;// connect to pTail->next
ListNode* newHead = NULL;// point to the first node of the merged list
if (NULL == pHead1){
return pHead2;
}else if(NULL == pHead2){
return pHead1;
}else{
// Determine the header pointer
if ( pHead1->data < pHead2->data){
newHead = pHead1;
pHead1 = pHead1->next;// point to the second node of the list
}else{
newHead = pHead2;
pHead2 = pHead2->next;
}
pTail = newHead;// point to the first node
while ( pHead1 && pHead2) {
if ( pHead1->data <= pHead2->data ){
pTail->next = pHead1;
pHead1 = pHead1->next;
}else {
pTail->next = pHead2;
pHead2 = pHead2->next;
}
pTail = pTail->next;
}
if(NULL == pHead1){
pTail->next = pHead2;
}else if(NULL == pHead2){
pTail->next = pHead1;
}
return newHead;
}
Copy the code5.4 Recursive scheme
5.4.1 Idea of problem solving
(1) Handle the existence of an empty linked list. If pHead1 is empty, pHead2 is returned, and pHead1 is returned if pHead2 is empty. (2) Compare the size of the first node of the two linked lists to determine the position of the head node. (3) After the head node is determined, continue to select the next node from the remaining nodes to link to the node selected in the second step, and then repeat steps (2) and (3) until there is no linked list.
5.4.2 Code implementation
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* newHead = NULL;
if (NULL == pHead1){
return pHead2;
}else if(NULL ==pHead2){
return pHead2;
}else{
if (pHead1->data < pHead2->data){
newHead = pHead1;
newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
}else{
newHead = pHead2;
newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
}
returnnewHead; }}Copy the code6 Deleting nodes in the linked list requires time complexity O(1)
6.1 Problem Description
Given a table header in a singly linked list and a node waiting to be deleted. Delete the linked list node at O(1) time complexity. After the node is deleted, the table header is returned.
Example: Given 1->2->3->4, and node 3, return 1->2->4.
6.2 Idea of problem solving
The most common way to remove a node from a singly linked list is to traverse the list, which is O(n) complexity. If we assign the value of the next node to be deleted to the node to be deleted, and then delete this node, it is equivalent to deleting the node to be deleted. Since it is easy to get the next node to delete the node, the complexity is O(1).
Example single linked list: 1->2->3->4->NULL To delete node 3. The first step assigns the value 4 of the next node of node 3 to the current node. Change to 1->2->4->4->NULL, and then delete 4. 1->2->4->NULL
If the node being removed is a head node, the head node points to NULL. If the last node is deleted, only the last node of the first node can be traversed from the beginning.
6.3 Graphical Process
6.4 Code Implementation
void deleteNode(ListNode **pHead, ListNode* pDelNode) {
if(pDelNode == NULL)
return;
if(pDelNode->next ! =NULL){
ListNode *pNext = pDelNode->next;
// Assign the value of the next node to the node to be deleted
pDelNode->val = pNext->val;
// The pointer to the node to be deleted is the second node behind it
pDelNode->next = pNext->next;
// Delete the next node of the node to be deleted
delete pNext;
pNext = NULL;
}else if(*pHead == pDelNode)// The deleted node is the head node
{
delete pDelNode;
pDelNode= NULL;
*pHead = NULL;
} else// Delete the last node
{
ListNode *pNode = *pHead;
while(pNode->next ! = pDelNode) { pNode = pNode->next; } pNode->next =NULL;
delete pDelNode;
pDelNode= NULL; }}Copy the codePrint the linked list from end to end
7.1 Fault Description
Enter a linked list and return an ArrayList in the order of list values from end to end.
7.2 solution
The element at the end of the list comes first, and the element at the head of the list comes after. It’s like fifo, fifO, fifO.
What data structures meet this requirement?
The stack!
7.2.1 Code implementation
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> value;
ListNode *p=NULL;
p=head;
stack<int> stk;
while(p! =NULL){
stk.push(p->val);
p=p->next;
}
while(! stk.empty()){ value.push_back(stk.top()); stk.pop(); }returnvalue; }};Copy the code7.3 solution to two
The second method is also easy to think of, through the structure of the linked list, if the end of the node is stored, the treatment of the rest of the list is still the same, so you can use the form of recursive processing.
7.3.1 Code implementation
class Solution {
public:
vector<int> value;
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p=NULL;
p=head;
if(p! =NULL) {if(p->next! =NULL){
printListFromTailToHead(p->next);
}
value.push_back(p->val);
}
returnvalue; }};Copy the codeReverse the linked list
8.1 Description
Reverse a single linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the codeAdvancements: You can iterate or recursively reverse linked lists. Can you solve the problem in two ways?
8.2 Solution idea
Set three nodes pre, CUR, and Next
- (1) Check each time
curWhether the node isNULLIf so, end the loop and get the result - (2) If
curThe node is notNULL, the temporary variable is set firstnextforcurThe next node of - (3)
curThe next node of the pointer becomes pointingpreAnd thenpremobilecur.curMove to thenext - (4) Repeat (1) (2) (3)
The demo
8.3 Code Implementation
8.3.1 Iterative mode
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur ! =NULL){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
returnpre; }};Copy the code8.3.2 Recursive processing
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// Recursive termination condition
if(head == NULL || head->next == NULL)
return head;
ListNode* rhead = reverseList(head->next);
// head->next now points to the end of the list after head
// head->next->next = head
head->next->next = head;
head->next = NULL;
returnrhead; }};Copy the code
End
Recently the article has a little like, if the article is helpful to you, please click a like ~