List of articles
203. Remove linked list elements
Give you a list of the head node head And an integer val , Please delete all the contents in the linked list Node.val == val The node of , And back to New head node .
Example 1：
Input ：head
= [
1,
2,
6,
3,
4,
5,
6],
val
=
6
Output ：[
1,
2,
3,
4,
5]
Example 2：
Input ：head
= [],
val
=
1
Output ：[]
Example 3：
Input ：head
= [
7,
7,
7,
7],
val
=
7
Output ：[]
Thought analysis
Double pointer
First for the original linked list Create a virtual header node ( Easy to operate ), Then define two pointers ,pre Point to previous node ,cur Point to the current node .
The current node meets the conditions , Then remove it .
Finally, delete the created virtual head node .
Graphic process :
Reference code
#include<bits/stdc++.h>
using
namespace
std;
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(
nullptr) {}
};
// Use double pointer
ListNode
*
removeElements(
ListNode
*
node,
int
val) {
ListNode
*
head
=
new
ListNode(
-
1,
node) ;
// Define header node
ListNode
*
pre
=
head;
// initialization
ListNode
*
cur
=
head
->
next;
// You can also use one directly here cur Variable to delete the node , We define two , Logic is clearer
ListNode
*
temp;
while(
cur
!=
NULL) {
if(
cur
->
val
==
val) {
temp
=
cur;
pre
->
next
=
cur
->
next;
cur
=
cur
->
next;
delete
temp;
}
else {
pre
=
cur;
cur
=
cur
->
next;
}
}
// Delete virtual head node
temp
=
head
->
next;
delete
head;
return
temp;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
206. Reverse a linked list
Here's the head node of the list head , Please reverse the list , And return the inverted linked list .
Example 1：
Input ：head
= [
1,
2,
3,
4,
5]
Output ：[
5,
4,
3,
2,
1]
Example 2：
Input ：head
= [
1,
2]
Output ：[
2,
1]
Example 3：
Input ：head
= []
Output ：[]
Thought analysis
Method 1 ： Double pointer
The basic idea : Change the direction of the pointer from front to back , Returns the last node
Use pre Point to previous node ,cur Represents the current node , Start traversing from the first node , Every time you let cur Point to pre, after cur Continue to traverse the next node , Until the linked list is traversed .
Method 2 ： recursive （ Change the direction of the pointer from front to back ）
Ideas and methods are basically the same , Recursion is actually calling itself , Each operation is consistent .
- Every time we need to change the pointer to , Two nodes need to be operated , Current node cur And the previous node pre, So this is the parameter of the recursive function .
- The end condition of recursion is The current node is NULL, There is no need to change direction . Recursion ends .
Method 3 ： recursive （ Change the direction of the pointer from back to front ）
Reference code
Method 1 ： Double pointer
// Method 1 : Double finger needling
ListNode
*
reverseList(
ListNode
*
head) {
if(
head
==
NULL
||
head
->
next
==
NULL) {
// Judge 0 And 1 A node situation , No inversion
return
head;
}
ListNode
*
pre
=
NULL,
*
cur
=
head,
*
temp
=
head
->
next;
// Start Change the pointer from front to back
while(
cur) {
temp
=
cur
->
next;
// Save the next node
cur
->
next
=
pre;
// Change direction
pre
=
cur;
//pre Move back
cur
=
temp;
//cur Move back
}
return
pre;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
Method 2 ： recursive ( Change the direction of the pointer from front to back )
// Method 2 : Recursive method 1 First change the direction of the pointer , Continue recursion
ListNode
*
reverse(
ListNode
*
pre,
ListNode
*
cur) {
// The return value is mainly used to return the header node after recursion , No other use
if(
cur
==
NULL) {
return
pre;
}
ListNode
*
temp
=
cur
->
next;
cur
->
next
=
pre;
// Modify pointer direction
return
reverse(
cur,
temp) ;
}
ListNode
*
reverseList(
ListNode
*
head) {
if(
head
==
NULL
||
head
->
next
==
NULL) {
// Judge 0 And 1 A node situation , No inversion
return
head;
}
return
reverse(
NULL,
head);
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
Method 3 ： recursive （ Change the direction of the pointer from back to front ） At present, the test fails …
// Method 3 : Recursive method 2 Recursion first , Then change the direction of the pointer ??? I don't know why I'm wrong ..
ListNode
*
resNode
=
new
ListNode(
-
1);
ListNode
*
solve(
ListNode
*
cur) {
if(
cur
==
NULL) {
// The end condition
return
resNode;
}
ListNode
*
pre
=
solve(
cur
->
next);
pre
->
next
=
cur;
return
cur;
}
ListNode
*
reverseList(
ListNode
*
head) {
if(
head
==
NULL
||
head
->
next
==
NULL) {
// Judge 0 And 1 A node situation , No inversion
return
head;
}
solve(
head);
ListNode
*
head
=
resNode
->
next;
delete
resNode;
return
head;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
24. Two or two exchange nodes in a linked list
Given a linked list , Two or two exchange the adjacent nodes , And return the list after exchange .
You can't just change the values inside the node , It needs to actually exchange nodes .
Example 1：
Input ：head
= [
1,
2,
3,
4]
Output ：[
2,
1,
4,
3]
Example 2：
Input ：head
= []
Output ：[]
Example 3：
Input ：head
= [
1]
Output ：[
1]
Thought analysis
The requirement of the topic is to exchange adjacent nodes , The title also says that the order of these two nodes has changed , Instead of just exchanging values . and If the current node has only one , Then there must be no need to exchange .
Next, we use diagrams to show :
According to the picture , We can use three auxiliary variables to complete the operation .
Reference code
#include<bits/stdc++.h>
using
namespace
std;
// Node definition
struct
ListNode{
int
val;
ListNode
*
next;
ListNode(){}
ListNode(
int
x):
val(
x),
next(
nullptr){
}
ListNode(
int
x,
ListNode
*
next):
val(
x),
next(
next){
}
};
ListNode
*
swapPairs(
ListNode
*
head) {
if(
head
==
NULL
||
head
->
next
==
NULL){
// When there is no node or only one node
return
head;
}
ListNode
*
dummyHead
=
new
ListNode(
-
1,
head);
// Create a virtual head node
ListNode
*
cur
=
dummyHead,
*
node1,
*
node2,
*
node3;
// Create the current node cur And auxiliary nodes node1、node2、node3
while(
cur
->
next
&&
cur
->
next
->
next){
node1
=
cur
->
next;
node2
=
cur
->
next
->
next;
node3
=
cur
->
next
->
next
->
next;
cur
->
next
=
node2;
// Take the first step : At present 0 The node points to 2 Node is no.
node2
->
next
=
node1;
// Go to step two : At present 2 The node points to 1 Node is no.
node1
->
next
=
node3;
// Go to step three : At present 1 The node points to 3 Node is no. .
cur
=
node1;
// to update cur
}
head
=
dummyHead
->
next;
delete
dummyHead;
return
head;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
19. Delete the last of the linked list N Nodes
I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .
Example 1：
Input ：head
= [
1,
2,
3,
4,
5],
n
=
2
Output ：[
1,
2,
3,
5]
Example 2：
Input ：head
= [
1],
n
=
1
Output ：[]
Example 3：
Input ：head
= [
1,
2],
n
=
1
Output ：[
1]
Thought analysis
Method 1 : Reverse thinking
Delete the last n Nodes ==> Delete positive number N-n+1 Nodes .
The illustration :( Take example 1 as an example )
Method 1 : Speed pointer
Start with a virtual head node , Convenient for our next operation .
- First step slow and fast All point to virtual head nodes .
- The second step fast Move forward n+1 Nodes
- slow and fast Moving forward at the same time , until fast It's empty , be slow The corresponding node is the previous node of the target node .
The illustration
Reference code
Method 1 : Reverse thinking
// Method 1 : Reverse thinking Delete the last n Nodes ==> Delete positive number N-n+1 Nodes .
ListNode
*
removeNthFromEnd(
ListNode
*
head,
int
n) {
ListNode
*
dummyHead
=
new
ListNode(
-
1,
head);
ListNode
*
cur,
*
temp;
cur
=
dummyHead
->
next;
int
N
=
0,
m;
// Summary point
while(
cur) {
N
++;
cur
=
cur
->
next;
}
// Delete the first n Nodes
m
=
N
-
n;
cur
=
dummyHead;
while(
m
--){
// The pointer points to m A place
cur
=
cur
->
next;
}
temp
=
cur
->
next;
// Save delete node
cur
->
next
=
cur
->
next
->
next;
// To delete
delete
temp;
// delete dummyHead;
head
=
dummyHead
->
next;
// final head Be sure to re assign the value , Because of the previous head May have hung up .
delete
dummyHead;
return
head;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
Method 2 : Double finger needling
// Method 2 : Double finger needling ( Fast and slow pointer method )
ListNode
*
removeNthFromEnd(
ListNode
*
head,
int
n) {
ListNode
*
dummyHead
=
new
ListNode(
-
1,
head);
ListNode
*
slow
=
dummyHead,
*
fast
=
dummyHead,
*
temp;
//fast Go ahead n+1 Step
while(
n
>=
0) {
fast
=
fast
->
next;
n
--;
}
//slow and fast Start walking at the same time , until fast by NULL
while(
fast
!=
NULL) {
slow
=
slow
->
next;
fast
=
fast
->
next;
}
// To delete
temp
=
slow
->
next;
slow
->
next
=
slow
->
next
->
next;
delete
temp;
head
=
dummyHead
->
next;
delete
dummyHead;
return
head;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
Interview questions 02.07. The list intersects
Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If there is no intersection between two linked lists , return null .
Figure two linked lists at the node c1 Start meeting ：
Subject data Guarantee There is no ring in the whole chain structure .
Be careful , Function returns the result , Linked list must Keep its original structure .
Example 1：
Input ：intersectVal
=
8,
listA
= [
4,
1,
8,
4,
5],
listB
= [
5,
0,
1,
8,
4,
5],
skipA
=
2,
skipB
=
3
Output ：Intersected
at
'8'
explain ： The value of the intersection node is 8 （ Be careful , If two linked lists intersect, they cannot be 0）.
Starting from the respective heads , Linked list A by [4,1,8,4,5], Linked list B by [5,0,1,8,4,5].
stay A in , There is... Before the intersection node 2 Nodes ; stay B in , There is... Before the intersection node 3 Nodes .
Example 2：
Input ：intersectVal
=
2,
listA
= [
0,
9,
1,
2,
4],
listB
= [
3,
2,
4],
skipA
=
3,
skipB
=
1
Output ：Intersected
at
'2'
explain ： The value of the intersection node is 2 （ Be careful , If two linked lists intersect, they cannot be 0）.
Starting from the respective heads , Linked list A by [0,9,1,2,4], Linked list B by [3,2,4].
stay A in , There is... Before the intersection node 3 Nodes ; stay B in , There is... Before the intersection node 1 Nodes .
Example 3：
Input ：intersectVal
=
0,
listA
= [
2,
6,
4],
listB
= [
1,
5],
skipA
=
3,
skipB
=
2
explain ： Starting from the respective heads , Linked list A by [2,6,4], Linked list B by [1,5].
Because these two linked lists don't intersect , therefore intersectVal It has to be for 0, and skipA and skipB It could be any value .
The two lists don't intersect , Therefore return null .
Thought analysis
The requirement of the topic is to find the intersection of two linked lists , But the intersection here is The pointers are equal , Not the same value in the node .
Look at the following two linked lists , at present curA Point to the list A Head node of ,curB Point to the list B Head node of , How to find the intersection .
We can find the length of two linked lists , And find the difference between the lengths of the two linked lists , And then let curA Move to , and curB End aligned position , Pictured ：
Now we can let CurA and CurB, Traverse the nodes of each linked list from front to back , Until they are equal , This corresponds to the intersection . If both linked lists are traversed and not found , Then there is no intersection .
Reference code
#include<bits/stdc++.h>
using
namespace
std;
struct
ListNode {
int
val;
ListNode
*
next;
ListNode() {}
ListNode(
int
x):
val(
x),
next(
nullptr) {
}
ListNode(
int
x,
ListNode
*
next):
val(
x),
next(
next) {
}
};
// Method : Double pointer
// First find the length of the two linked lists , Then the longest two pointers point to the shortest starting position , Move back at the same time . Know that when you encounter a public node
ListNode
*
getIntersectionNode(
ListNode
*
headA,
ListNode
*
headB) {
ListNode
*
pointerA
=
headA,
*
pointerB
=
headB;
int
lenA
=
0,
lenB
=
0,
gap;
//a:b Represents the length of two linked lists
while(
pointerA) {
// seek LenA length
lenA
++;
pointerA
=
pointerA
->
next;
}
while(
pointerB) {
// seek LenB length
lenB
++;
pointerB
=
pointerB
->
next;
}
Always let A Length ratio of B Big
if(
lenA
>
lenB) {
pointerA
=
headB;
pointerB
=
headA;
gap
=
lenA
-
lenB;
}
else{
pointerA
=
headA;
pointerB
=
headB;
gap
=
lenB
-
lenA;
}
while(
gap
--) {
//B The pointer moves to and A The same position as the pointer
pointerB
=
pointerB
->
next;
}
while(
pointerA
&&
pointerB) {
//A and B Move forward together
if(
pointerA
==
pointerB){
// If it is the same, return directly
return
pointerA;
}
pointerA
=
pointerA
->
next;
pointerB
=
pointerB
->
next;
}
return
NULL;
// If there is no public node , Then return to NULL;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
141. Circular list
Give you a list of the head node head , Judge whether there are links in the list .
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list .
If there are rings in the list , Then return to true . otherwise , return false .
Example 1：
Input ：head
= [
3,
2,
0,
-
4],
pos
=
1
Output ：true
Example 2：
Input ：head
= [
1,
2],
pos
=
0
Output ：true
Example 3：
Input ：head
= [
1],
pos
=
-
1
Output ：false
Thought analysis
How to judge whether there is a ring ?: Speed pointer
Defining the fast and slow The pointer , Point to the head node respectively ,fast Move two nodes at a time ,slow Move one node at a time , If fast and slow The hands meet on the way , It shows that the linked list has links .
It's like running on the playground , A fast runner will catch up with a slow runner after a period of time .
Reference code
#include<bits/stdc++.h>
using
namespace
std;
struct
ListNode {
int
val;
ListNode
*
next;
ListNode() {}
ListNode(
int
x):
val(
x),
next(
nullptr) {
}
ListNode(
int
x,
ListNode
*
next):
val(
x),
next(
next) {
}
};
bool
hasCycle(
ListNode
*
head) {
ListNode
*
slow
=
head,
*
fast
=
head;
while(
fast
!=
NULL){
fast
=
fast
->
next;
if(
fast
!=
NULL) {
fast
=
fast
->
next;
}
else{
// No ring
continue;
}
slow
=
slow
->
next;
if(
slow
==
fast){
// Ring
return
true;
}
}
return
false;
// No ring
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
142. Circular list II
Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .
No modification allowed Linked list .
Example 1：
Input ：head
= [
3,
2,
0,
-
4],
pos
=
1
Output ： The return index is
1
explain ： There is a link in the list , Its tail is connected to the second node .
Example 2：
Input ：head
= [
1,
2],
pos
=
0
Output ： The return index is
0
explain ： There is a link in the list , Its tail is connected to the first node .
Example 3：
Input ：head
= [
1],
pos
=
-
1
explain ： There are no links in the list .
Thought analysis
This paper mainly studies :
- Determine whether the linked list is a ring
- If there are rings , How to find the entrance of this ring
How to judge whether there is a ring ?: Speed pointer
Defining the fast and slow The pointer , Point to the head node respectively ,fast Move two nodes at a time ,slow Move one node at a time , If fast and slow The hands meet on the way , It shows that the linked list has links .
It's like running on the playground , A fast runner will catch up with a slow runner after a period of time .
If there are rings , How to find the entrance of this ring %22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3F%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E)
Start a pointer from the beginning node index1, From the meeting node Also start a pointer index2, These two pointers walk only one node at a time , So when these two pointers meet, it is The node of the ring entrance .
The proof process can refer to boss Carl's article , It's easy to understand , Hey, hey, hey
Reference code
#include<bits/stdc++.h>
using
namespace
std;
struct
ListNode {
int
val;
ListNode
*
next;
ListNode() {}
ListNode(
int
x):
val(
x),
next(
nullptr) {
}
ListNode(
int
x,
ListNode
*
next):
val(
x),
next(
next) {
}
};
ListNode
*
detectCycle(
ListNode
*
head) {
ListNode
*
slow
=
head,
*
fast
=
head,
*
index1,
*
index2;
// First, judge whether there is a ring or not
while(
fast
!=
NULL
&&
fast
->
next
!=
NULL) {
fast
=
fast
->
next
->
next;
//fast Take two steps
slow
=
slow
->
next;
//slow Take a step
if(
slow
==
fast) {
// At this time, if you meet, it must be the entry node
index1
=
head;
index2
=
slow;
// Look for the entrance of the ring
while(
index1
!=
index2) {
index1
=
index1
->
next;
index2
=
index2
->
next;
}
return
index1;
}
}
return
NULL;
// If acyclic , You'll quit while loop , return NULL
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
707. Design the list
Design the realization of linked list . You can choose to use single or double linked list . Nodes in a single chain table should have two properties ：val and next.val Is the value of the current node ,next Is a pointer to the next node / quote . If you want to use a two-way linked list , Then you need an attribute prev To indicate the last node in the list . Suppose that all nodes in the list are 0-index Of .
Implement these functions in the linked list class ：
- get(index)： Get the index Values of nodes . If the index is invalid , Then return to -1.
- addAtHead(val)： Add a value of... Before the first element of the list val The node of . After inserting , The new node will be the first node in the list .
- addAtTail(val)： Will be worth val To the last element of the list .
- addAtIndex(index,val)： In the list, the index The value added before nodes is val The node of . If index It's equal to the length of the list , Then the node will be attached to the end of the list . If index Greater than the length of the list , The node will not be inserted . If index Less than 0, Then insert the node in the head .
- deleteAtIndex(index)： If the index index It works , Delete the index Nodes .
Thought analysis
It's very possible to guess this blindly , Very basic .
Example ：
MyLinkedList
linkedList
=
new
MyLinkedList();
linkedList.
addAtHead(
1);
linkedList.
addAtTail(
3);
linkedList.
addAtIndex(
1,
2);
// Linked list becomes 1-> 2-> 3
linkedList.
get(
1);
// return 2
linkedList.
deleteAtIndex(
1);
// Now the list is 1-> 3
linkedList.
get(
1);
// return 3
Reference code
#include<bits/stdc++.h>
using
namespace
std;
// It's strange , It's supposed to be ok ...
class
MyLinkedList {
public:
// Define linked list
struct
LinkedNode {
int
val;
LinkedNode
*
next;
LinkedNode():
val(
0),
next(
NULL) {
};
LinkedNode(
int
x):
val(
x),
next(
NULL) {
};
LinkedNode(
int
x,
LinkedNode
*
next):
val(
x),
next(
next) {
};
};
MyLinkedList() {
head
=
new
LinkedNode();
size
=
0;
}
// Get linked list index Values of nodes . If the index is invalid , Then return to -1.
int
get(
int
index) {
if(
index
<
0
||
index
>
size
-
1 ) {
return
-
1;
}
LinkedNode
*
cur
=
head
->
next;
while(
index
--) {
// It's actually getting index+1 Nodes , because index It's from 0 At the beginning
cur
=
cur
->
next;
}
return
cur
->
val;
}
// Add nodes to the head of the list .
void
addAtHead(
int
val) {
// ListNode *newNode = new ListNode(val,head->next);
// head->next = newNode;
head
->
next
=
new
LinkedNode(
val,
head
->
next);
size
++;
}
// Add nodes at the end of the list
void
addAtTail(
int
val) {
LinkedNode
*
cur
=
head;
while(
cur
->
next) {
cur
=
cur
->
next;
}
cur
->
next
=
new
LinkedNode(
val);
size
++;
}
// In the list, the index The value added before nodes is val The node of .
// If index It's equal to the length of the list , Then the node will be attached to the end of the list
// If index Greater than the length of the list , The node will not be inserted .
// If index Less than 0, Then insert the node in the head .
void
addAtIndex(
int
index,
int
val) {
if(
index
>
size) {
// If index Greater than the length of the list , The node will not be inserted .
return;
}
if(
index
<
0) {
// If index Less than 0, Then insert the node in the head .
addAtHead(
val);
}
if(
index
==
size) {
// If index It's equal to the length of the list , Then the node will be attached to the end of the list
addAtTail(
val);
}
LinkedNode
*
cur
=
head;
while(
index
--) {
cur
=
cur
->
next;
}
cur
->
next
=
new
LinkedNode(
val,
cur
->
next);
// ListNode *newNode = new ListNode(val);
// newNode->next = cur->next;
// cur->next = newNode;
size
++;
}
// If the index index It works , Delete the index Nodes .
void
deleteAtIndex(
int
index) {
if(
index
>=
size
||
index
<
0) {
return;
}
LinkedNode
*
cur
=
head;
while(
index
--) {
cur
=
cur
->
next;
}
LinkedNode
*
temp
=
cur
->
next;
cur
->
next
=
cur
->
next
->
next;
delete
temp;
size
--;
}
void
printLinkedList(){
LinkedNode
*
cur
=
head;
while(
cur
->
next){
cout
<<
cur
->
next
->
val
<<
" ";
cur
=
cur
->
next;
}
cout
<<
endl;
}
private:
// Global variables
LinkedNode
*
head;
int
size ;
};
int
main() {
MyLinkedList
*
obj
=
new
MyLinkedList();
int
param_1
=
obj
->
get(
0);
cout
<<
param_1
<<
endl;
obj
->
addAtHead(
1);
obj
->
printLinkedList();
obj
->
addAtTail(
2);
obj
->
printLinkedList();
obj
->
addAtIndex(
1,
3);
obj
->
printLinkedList();
obj
->
deleteAtIndex(
0);
obj
->
printLinkedList();
return
0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
- 81.
- 82.
- 83.
- 84.
- 85.
- 86.
- 87.
- 88.
- 89.
- 90.
- 91.
- 92.
- 93.
- 94.
- 95.
- 96.
- 97.
- 98.
- 99.
- 100.
- 101.
- 102.
- 103.
- 104.
- 105.
- 106.
- 107.
- 108.
- 109.
- 110.
- 111.
- 112.
- 113.
- 114.
- 115.
- 116.
- 117.
- 118.
- 119.
- 120.
- 121.
- 122.
- 123.
- 124.
remarks : There's nothing wrong with the code itself ,LeetCode The question may be a little lax …
If there is harvest ！！！ I hope the old fellow will have three links. , give the thumbs-up 、 Collection 、 forward .
It's not easy to create , Don't forget to like it , It can be seen by more people article , By the way, encourage me to write a better blog
