Linked list
- Single list
- Double linked list
- circular linked list
Storage method in memory: The addresses are not continuous and are connected through pointers in the pointer fields of nodes.
Applicable scenarios: The amount of data is not fixed, there are many additions and deletions, and there are few queries.
Definition of linked list
//Singly linked list
struct ListNode {
int val; // elements stored on the node
ListNode *next; // Pointer to the next node
ListNode(int x) : val(x), next(NULL) {} // Constructor of node
};
Remove linked list elements
Title: Leetcode203
Solution 1: Use the original linked list directly
- Time complexity: O(n)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//Directly use the original linked list to perform the deletion operation
//Disadvantages: Need to judge the head node separately
ListNode* tmp = NULL;
//There may be multiple consecutive nodes that need to be deleted starting from the head node, so you need to use while
while(head & amp; & amp; head->val == val) {
tmp = head;
head = head->next;
delete tmp;
}
ListNode* prev = head;//The deleted node must be able to find the predecessor node and delete it with the help of the predecessor node
//Delete non-head nodes
while(prev & amp; & amp; prev->next) {
tmp = prev->next;
if(tmp->val == val) {
prev->next = tmp->next;
delete tmp;
}
else {
prev = prev->next;
}
}
return head;
}
};
Solution 2: Use virtual header node
- Time complexity: O(n)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(): val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//Virtual header node
//Advantages: No need to judge the head node separately
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* prev = dummyhead;
while(prev->next) {
ListNode* tmp = prev->next;
if(tmp->val == val) {
prev->next = tmp->next;
delete tmp;
}
else {
prev = prev->next;
}
}
//The head node may have been deleted, so it needs to be reset to the next node of dummyhead
head = dummyhead->next;
delete dummyhead;
return head;
}
};
Design linked list
Title: Leetcode707
Virtual header nodes are also used.
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val): val(val), next(nullptr) {}
};
MyLinkedList() {
_dummyhead = new LinkedNode(0);//Initialize the virtual head node
_size = 0;
}
int get(int index) {
//Determine whether the index is legal. If it is not legal, -1 will be returned. The index starts from 0.
if(index > (_size - 1) || index < 0) {
return -1;
}
//Traverse starting from the head node, and each node traversed is index-1. When the index is 0, it happens to be the node with the subscript index.
//while(index--) should be remembered
LinkedNode* tmp = _dummyhead->next;
while(index--) {
tmp = tmp->next;
}
return tmp->val;
}
void addAtHead(int val) {
LinkedNode* newhead = new LinkedNode(val);
//Insert a new head node. The actual operation is to insert it between the virtual head node and the original head node.
newhead->next = _dummyhead->next;
_dummyhead->next = newhead;
_size + + ;
}
void addAtTail(int val) {
LinkedNode* tail = new LinkedNode(val);
LinkedNode* tmp = _dummyhead;
while(tmp->next) {
tmp = tmp->next;
}
tmp->next = tail;
_size + + ;
}
//Insert a new node before the index node, for example, if index is 0, then the newly inserted node is the new head node of the linked list.
// If index is equal to the length of the linked list, it means that the newly inserted node is the tail node of the linked list.
// If index is greater than the length of the linked list, return empty
// If index is less than 0, insert node at the head
void addAtIndex(int index, int val) {
//Determine whether the index is legal
if(index > _size) return;
if(index < 0 ) index = 0;
//Traverse the index nodes starting from the virtual head node, which is exactly the node before the index node
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* tmp = _dummyhead;
while(index--) {
tmp = tmp->next;
}
newNode->next = tmp->next;
tmp->next = newNode;
_size + + ;
}
void deleteAtIndex(int index) {
//Determine whether the index is legal
if(index >= _size || index < 0) return;
LinkedNode* tmp = _dummyhead;
while(index--) {
tmp = tmp->next;
}
LinkedNode* target = tmp->next;
tmp->next = tmp->next->next;
delete target;
//The delete command indicates that the part of memory originally pointed to by the tmp pointer is released.
//The value (address) of the deleted pointer tmp is not NULL, but a random value. That is, after being deleted,
//If you don't add tmp=nullptr, tmp will become a wild pointer.
//If the subsequent program accidentally uses tmp, it will point to an unpredictable memory space.
target = nullptr;
_size--;
}
private:
int _size;
LinkedNode* _dummyhead;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
*MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
Flip the linked list
Title: Leetcode206
Idea: Change the pointing of the next pointer of the linked list and directly flip the linked list
Solution 1: Use the characteristics of the stack
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(): val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
stack<int> s;
ListNode* tmp = head;
while(tmp) {
s.push(tmp->val);
tmp = tmp->next;
}
tmp = head;
while(!s.empty()) {
tmp->val = s.top();
s.pop();
tmp = tmp->next;
}
return head;
}
};
Solution 2: Double pointers
- Time complexity: O(n)
- Why should we save temporary nodes?
- Because the next step is to change the direction of cur->next and point cur->next to pre. At this time, the first node has been reversed.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(): val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
ListNode* tmp = cur->next;//Save the next node
cur->next = pre;//Change the pointer pointing
//To move the pointer, pre must be moved first, otherwise if cur changes first, an error will occur in the pre update.
pre = cur;
cur = tmp;
}
return pre;
}
};
Solution 3: Recursion
It’s the same logic as the double pointer method
- Time complexity: O(n), each node of the linked list needs to be processed recursively
- Space complexity: O(n), recursively calling n levels of stack space
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(): val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur) {
if(cur == NULL) return pre;
ListNode* tmp = cur->next;//Save the next node
cur->next = pre;//Change the pointer pointing
//To move the pointer, pre must be moved first, otherwise if cur changes first, an error will occur in the pre update.
//The way to write recursion is actually to do these two steps.
//pre = cur;
//cur = tmp;
return reverse(cur, tmp);
}
ListNode* reverseList(ListNode* head) {
//ListNode* cur = head;
//ListNode* pre = NULL;
return reverse(NULL, head);
}
};
Summary
Virtual head nodes and recursion still require more practice and understanding.
Reference link
Code Random Notes: Basics of linked list theory, removing linked list elements, designing linked lists, flipping linked lists