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; }