## Single list

```class MyLinkedList {
public:

struct Node{
int val;
struct Node *next;
Node(int x):val(x),next(NULL){};
};

int length;

length = 0;
}

int get(int index) {
if(index<0 || index>length-1) return -1;
int i = 0;
while(p && i<index){
p = p->next;
i++;
}
if(!p || i>index){
return -1;
}
return p->val;
}

Node *new_node = new Node(val);
// new_node->val = val;
new_node->next = p->next;
p->next = new_node;
length++;
}

Node *q = new Node(val);
while(p->next){
p = p->next;
}
p->next = q;
length++;
}

void addAtIndex(int index, int val) {
if(index<0 || index>length) return ;
Node *new_node = new Node(val);
int i = 0;

while(p && i<index){
p = p->next;
i++;
}
if(!p || i>index){
return ;
}
new_node->next = p->next;
p->next = new_node;
length++;
}

void deleteAtIndex(int index) {
if(index<0||index>=length) return ;
int i = 0;
while(p && i<index){
p = p->next;
i++;
}
p->next = p->next->next;
length--;
}
};

/**
* int param_1 = obj->get(index);
* obj->deleteAtIndex(index);
*/
```

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Determine whether there is a ring: use the fast and slow pointer

The slow pointer takes one step at a time, and the fast pointer takes two steps each time. If they meet, it means that there is a ring. If one is empty, it means that there is no ring.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(fast && slow && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow) return true;
}
return false;
}
};
```

Determine if there is a ring

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//find the meeting point
while(fast && slow && fast->next){
fast = fast->next->next;
slow = slow->next;
//first encounter
if(fast == slow) break;
}
//Determine if there is a ring
if(!fast || !fast->next) return NULL;
while(fast != slow){
//one step at a time
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
```

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Concatenate two linked lists, compare them, and find the same node. is equivalent to:

After searching in A, go to B, and after B, go to A.

```class Solution {
public:
int cnt=0;
while(p1&&p2){

p1=p1->next;
p2=p2->next;
if(p1==p2){return p1;}
if(cnt<2&&!p1){
cnt++;
}
if(cnt<2&&!p2){
cnt++;
}
}
return NULL;
}
};
```

### Delete the N th node from the bottom of the linked list

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Fast and slow pointers

```/**
* 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* removeNthFromEnd(ListNode* head, int n) {
int i = 0;
//fast moves forward n steps, when fast goes to the end, slow goes to the node to be deleted
while(i < n){
fast = fast->next;
i++;
}
if(!fast) return head->next;//If fast is empty, it means that the head node is deleted
//Find the previous node of the node to delete
while(fast->next){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
}
};
```

(The head node is the first node)

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

• Method 1: Iteration

Iterate over nodes in original order and move them one by one to the head of the 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 *q = nullptr;
while(p->next){
q = p->next;
p->next = q->next;
}
}
};
```
• Method 2: Stack

```/**
* 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:
stack<ListNode> s;
while(p){
s.push(p);
p = p->next;
}
if(stack.empty()) return nullptr;
ListNode *L = nullptr;
ListNode *node = L;
while(!s.empty()){
ListNode *temp = s.top();
node->next = temp;
node = node->next;
s.pop();
}
node->next = nullptr;
return L->next;
}
};
```
• Method 3: Recursive

```/**
* 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:
//The linked list is empty, or the linked list has no tail node
//Save the next node of the current node
//Reverse the linked list starting from the next node of the current node
//reverse is the linked list after the reverse, so the next after the reverse is the end node of the reverse
ListNode *reverse = reverseList(next);
//Hang the current node head after the tail node
//The current node becomes the tail node
return reverse;
}
};
```

tail recursion

Although tail recursion will continue to push the stack, but because the value of the recursive function is finally returned, it will pop out of the stack at one time when returning, and it will not be so slow to pop out of the stack one by one.

Add nodes one by one to the front of the reversed 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:

}
}
};
```

## remove list element

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

• Method 1: Iteration

```/**
* 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) {
while(p && p->next){
if(p->next->val == val){
p->next = p->next->next;
continue;
}
p = p->next;
}
}
}
};
```
• Method 2: Recursion

```/**
* 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) {
//If there is val, delete and return head->next after removing a node, otherwise return head directly, that is, the entire sub-linked list
}
};
```

Linked List - LeetBook - LeetCode Technology Growth Platform Loved by Global Geeks

Move two steps at a time, linking the same odd or even nodes

```/**
* 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:
}

int i = 1;
while(odd && even && odd->next && even->next){
ListNode *target = even->next;
even->next = even->next->next;
even = even->next;
target->next = odd->next;
odd->next = target;
odd = odd->next;
}
}
};
```

• Method 1: Reverse the second half

Find the end of the linked list through the fast and slow pointer, reverse the second half, and compare whether the two linked lists are equal.

```/**
* 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:

while(fast->next && fast->next->next){//The number of linked list nodes may be odd or even
slow = slow->next;
fast = fast->next->next;
}
if(fast->next && fast->next->next == nullptr){//When there are an even number of nodes, the end point is moved forward by one, and the linked list is separated from 1/2 and 1/2+1 to facilitate the comparison of the second half after the inversion. If it is an odd number, the linked list is moved from 1/2+  1 split, directly reverse the second half
slow = slow->next;
}
ListNode* rev = reverse(slow);//reverse

//Compare
while(rev){
rev = rev->next;
}
return true;

}

ListNode *prev = nullptr;

}
// cout<<prev->val;
return prev;
}
};
```
• Method 2: Stack

The node is pushed onto the stack and compared with the linked list elements when popped.

```/**
* 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:
stack<ListNode*> s;
while(p){
s.push(p);
p = p->next;
}
ListNode *temp = s.top();
s.pop();
}
return true;
}
};
```
• Method 3: Recursive

```/**
* 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 *temp;
}

temp = temp->next;
return res;
}
};
```

```class MyLinkedList {
public:
struct Node{
int val;
Node *next;
Node *prev;
Node(int _val){
val = _val;
prev = NULL;
next = NULL;
}
};
int size;
size = 0;
}

int get(int index) {
if(index < 0 || index >= size) return -1;
int i = 0;
while(i<index && p){
p = p->next;
i++;
}
return p->val;
}

Node *p = new Node(val);
size++;
}

Node *p = new Node(val);
while(L->next){
L = L->next;
}
L->next = p;
p->prev = L;
p->next = NULL;
size++;
}

void addAtIndex(int index, int val) {
if(index <= 0){
}else if(index == size){
}else if(index > size){
return ;
}else{
Node *p = new Node(val);
int i = 0;
while(i<index && L){
L = L->next;
i++;
}
if(!L || i>index){
return ;
}
p->next = L;
p->prev = L->prev;
L->prev->next = p;
L->prev = p;
size++;
}
}

void deleteAtIndex(int index) {
if(index<0 || index>=size){
return ;
}
int i = 0;
while(i<index && L){
L = L->next;
i++;
}
if(L->next){
L->next->prev = L->prev;
// L->prev->next = L->next;
}
L->prev->next = L->next;
delete L;
i++;
size--;
}
};

/**
* int param_1 = obj->get(index);
* obj->deleteAtIndex(index);
*/
```

## other

### Merge two sorted linked lists

• method one

```/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *new_list = new ListNode();
while(list1 && list2){
if(list1->val < list2->val){
new_list->next = list1;
list1 = list1->next;
}else{
new_list->next = list2;
list2 = list2->next;
}
cout<<new_list->val<<endl;
new_list = new_list->next;
}
new_list->next = list1 ? list1 : list2;
}
};
```
• Method 2: Recursion

```/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2;
if(!list2) return list1;

if(list1->val < list2->val){
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next = mergeTwoLists(list2->next,list1);
return list2;
}
}
};
```

```/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
int sum = 0;
while(l1 || l2 || carry){
sum = 0;
if(l1){
sum += l1->val;
l1 = l1->next;
}
if(l2){
sum += l2->val;
l2 = l2->next;
}
ListNode *p = new ListNode();
p->val = (sum + carry) % 10;
new_list->next = p;
new_list = new_list->next;
carry = (sum + carry) / 10;
}