catalogue
Knowledge points:
Linked list: a linear structure in which pointers are connected in series. Each node contains a pointer field and a data field.
Type: single linked list (each node points to the next node), double linked list (each node refers to the forward node and rear node), circular linked list (the linked list is connected end to end).
Delete and add: the time complexity is O(1), but the time complexity of finding is O(n). As opposed to arrays.
Code template summary:
1. Definition and calling method of linked list:
//definition
struct ListNode {
int val; // Elements stored by nodes
ListNode *next； // Pointer to the next node
ListNode(int x) : val (x), next(NULL) {} // Constructor of node
};
//Construct initialization node
ListNode* head = new ListNode(5);1. Virtual node definition
When it comes to the deletion of the linked list, we can set a virtual node to point to the head node of the linked list, so that we can perform the same deletion operation for the whole linked list instead of dealing with the head node separately.
//Set the virtual node, which refers to the head node
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
//Query the entire linked list
ListNode* cur = dummyHead;
while (cur->next != NULL) {
}
//Delete virtual node
head = dummyHead->next;
delete dummyHead;
return head;
2. Switching node
Some nodes need to be reserved and some nodes need to be changed,
Save is temp (temporary) = cur (current); Change nodes with cur = temp.
/*When saving nodes, temp... = cur*/ ListNode* temp = cur->next; ListNode* temp1 = cur->next->next; ListNode* temp2 = cur->next->next->next; /*When changing nodes, cur... = temp*/ cur->next = temp1; cur->next->next = temp; cur->next->next->next = temp2;
3. Find node operation
//Find the length of linked list A
int lenA = 0;
while(curA != NULL) {
lenA++;
curA = curA->next;
}
//Find the node at index
LinkedNode* cur = dummyNode->next;
while(index--) {
cur = cur->next;
}
//Traverse the current linked list (nodes may be added at the end)
LinkedNode* cur = dummyNode;
while(cur->next!=NULL) {
cur = cur->next;
}
cur->next = newNode;Question:
203. Remove the linked list element LeetCode (LeetCode CN. Com)
Note: 1. Remember to release memory during c + + delete node operation.
2. Set up a virtual node to remove the head node and other nodes in the same way.
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//Set virtual node
ListNode* dummyHead = new ListNode(0);
//Virtual node refers to the head node
dummyHead->next = head;
//Query the entire linked list
ListNode* cur = dummyHead;
while (cur->next != NULL) {
//If it's that value
if (cur->next->val == val) {
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
} else {
cur = cur->next;
}
}
//Delete virtual node
head = dummyHead->next;
delete dummyHead;
return head;
}
};707. Design linked list - LeetCode (LeetCode CN. Com)
class MyLinkedList {
public:
//Define the linked list structure. The structure is a large hump, and there is a semicolon at the end of the structure
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int x):val(x), next(NULL){}
};
//Initialize linked list
MyLinkedList() {
//Define a virtual node, not a real head node
dummyNode = new LinkedNode(0);
size = 0;
}
//Get the value of the index node in the linked list
int get(int index) {
//Judge whether the limit is exceeded
if(index > size - 1 || index < 0) {
return -1;
}
LinkedNode* cur = dummyNode->next;
//Query list
while(index--) {
cur = cur->next;
}
return cur->val;
}
// Insert a node at the front of the linked list. After the insertion, the newly inserted node is the new head node of the linked list
void addAtHead(int val) {
//Define a new node
LinkedNode* newNode = new LinkedNode(val);
//Point to the head node behind the virtual node
newNode->next = dummyNode->next;
//The virtual node points to this node
dummyNode->next = newNode;
//Length++
size++;
}
// Add a node at the end of the linked list
void addAtTail(int val) {
//Define a new node
LinkedNode* newNode = new LinkedNode(val);
//Query the current linked list
LinkedNode* cur = dummyNode;
while(cur->next!=NULL) {
cur = cur->next;
}
cur->next = newNode;
//Length + + (remember)
size++;
}
/*Add a node with a value of # val # before the # index # node in the linked list.
If "index" is equal to the length of the linked list, the node will be attached to the end of the linked list.
If the index is greater than the length of the linked list, the node will not be inserted.
If the index is less than 0, the node is inserted in the header.*/
void addAtIndex(int index, int val) {
if(index > size) { return;}
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = dummyNode;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
size++;
}
//If the index is valid, delete the index node in the linked list.
void deleteAtIndex(int index) {
//Judge whether it is valid. It can be equal to the current length
if(index >= size || index < 0) return;
//Define virtual nodes
//LinkedNode* dummyNode = newNode* dummyNode;
//Current node (first error)
LinkedNode* cur = dummyNode;
//lookup
while (index--) {
cur = cur->next;
}
//Find the node
LinkedNode* temp = cur->next;
cur->next = temp->next;
//Release and subtract one
delete temp;
size--;
}
//Print linked list
void printLinkList() {
//Define node
LinkedNode * cur = dummyNode;
//lookup
while (cur->next != NULL) {
cout << cur->next->val <<" ";
cur = cur->next;
}
cout <<endl;
}
//Note that private members are also defined
private:
int size;
LinkedNode* dummyNode;
};
Many foundations in the linked list are more important.
24. Exchange the nodes in the linked list - LeetCode (LeetCode CN. Com)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyNode = new ListNode(0);
dummyNode->next = head;
ListNode* cur = dummyNode;
while(cur->next != nullptr && cur->next->next != nullptr) {
/*When saving nodes, temp... = cur*/
// Save temporary nodes 1, 2 and 3
ListNode* temp = cur->next;
ListNode* temp1 = cur->next->next;
ListNode* temp2 = cur->next->next->next;
/*When changing nodes, cur... = temp*/
//Step 1
cur->next = temp1;
//Step 2
cur->next->next = temp;
//Step 3
cur->next->next->next = temp2;
//Move back two places
cur = cur->next->next;
}
return dummyNode->next;
}
};This involves the exchange between many nodes and needs to be saved,
Save is temp (temporary) = cur (current); Change nodes with cur = temp. There will be no mistakes.
19. Delete LeetCode (leetcode-cn.com), the penultimate node in the linked list
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyNode = new ListNode(0);
dummyNode->next = head;
ListNode* cur = dummyNode;
ListNode* temp = dummyNode;
int size = 0;
//Come on, the pointer has come to an end
while(cur->next != 0) {
size++;
//The slow pointer takes n steps less than the fast pointer
if(size > n) {
temp = temp->next;
}
cur = cur->next;
}
ListNode* temp2;
temp2 = temp->next;
temp->next = temp->next->next;
delete temp2;
return dummyNode->next;
}
};Error: don't return head when returning the head node. If there is no chain header node, use the virtual node.
Interview question 02.07 Linked list intersection force buckle (LeetCode) (LeetCode CN. Com)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0, dif = 0;
//Find the length of linked list A
while(curA != NULL) {
lenA++;
curA = curA->next;
}
//Find the length of linked list B
while(curB != NULL) {
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
//Find the length difference, assuming that the largest is A
if(lenA < lenB) {
swap(lenA, lenB);
swap(curA, curB);
}
dif = lenA - lenB;
//The tail position is opposite to it, that is, the length difference of the long linked list moving forward
while(dif--) {
curA = curA->next;
}
//Traversal array
while(curA != NULL) {
if(curA == curB)
return curA;
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};Error: 1. When judging the node length, using cur - > next will cause the array to be exceeded.
2. This problem is that two nodes are equal, that is, the pointer is the same, not the value is the same.
142. Ring linked list II - LeetCode (LeetCode CN. Com)
Judge whether there is a ring: define the speed pointer. fast takes two nodes and slow takes one node. If there is a ring, it will meet in the ring.
Meeting place: start a pointer from the beginning node and start a pointer from the meeting node. The two pointers only go to one node at a time. Then when the two pointers meet, they are the nodes of the ring entrance.
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
ListNode* meet = fast;
ListNode* start = head;
while(meet != start) {
meet = meet->next;
start = start->next;
}
return meet;
}
}
return NULL;
}