前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。（卡哥这道题，void addAtIndex(int index, int val) 方法中对于 index < 0 情况直接return;这样的处理不符合题目意思，index < 0,题目意思为将值为val的节点当头结点插入）
代码随想录此题链接

题目

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示：

所有val值都在 [1, 1000] 之内。
操作次数将在 [1, 1000] 之内。
请不要使用内置的 LinkedList 库。

1. 设计链表(增删改查)

思路

分两种，一种是含有虚拟头结点，一种不含有虚拟头节点，因为含有虚拟头节点的处理更加通用，故只介绍含有虚拟头节点的方式。

需要的变量:

1. 定义类
2. 定义链表结构的结构体struct
3. 类中的变量，虚拟头节点 dummyHead指针，以及链表的长度

2. 本题思路分析：

1. 首先要创建一个链表类，类中有一个结构体用于初始化链表，有两个私有化参数，一个是虚拟头节点，另一个是链表的长度。
2. 在对index位置的元素进行操作时，循环可以用while(index–)的形式。
3. 对于创建C++类，以及调用类的对象，类的方法，可以参考这篇文章C++类的介绍。
4. 实现不难，主要就是内容多，需要比较仔细。

3. 算法实现

• 代码：

#include
#include
using namespace std;
class MyLinkedList{
	public:
		struct LinkedList{
			int val;
			LinkedList* next;
			LinkedList():val(0),next(nullptr){}
			LinkedList(int val):val(val),next(nullptr){}
			LinkedList(int val,LinkedList* next):val(val),next(next){}
		};
		
		MyLinkedList(){
			_size = 0;
			_dummy = new LinkedList();
		}
		
		//获取链表中第 index 个节点的值。如果索引无效，则返回-1。
		int get(int index) {
			if(index < 0 || index > (_size - 1)){
				//此时索引超出了范围
				return -1; 
			}
			LinkedList* cur = _dummy -> next;//这里是next 
			while(index--){
				cur = cur -> next;
			}
			return cur -> val;
		}
		
		//在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
		void addAtHead(int val) {
			LinkedList* newHead = new LinkedList(val);//插入值需要创建新节点
			newHead -> next = _dummy -> next;
			_dummy -> next = newHead;
			_size++;//易错点,非常容易忘记对于_size的操作 
		}
		
		//addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
		void addAtTail(int val) {
			LinkedList* newHead = new LinkedList(val);
			LinkedList* cur = _dummy;
			while(cur -> next !=  nullptr){
				//到最后一个节点 
				cur = cur -> next;
			}
			cur -> next = newHead;
			_size++;//易错点,非常容易忘记对于_size的操作 
		}
		
		//addAtIndex(index,val)：在链表中的第index个节点之前添加值为val的节点。
		//如果index等于链表的长度，则该节点将附加到链表的末尾。
		//如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
		void addAtIndex(int index, int val) {
			if(index > _size){
				//长度大于等于链表长度  (易错点：可以等于链表长度，所以这里可以不要_size-1)
				return;
			}else if(index < 0){
				//index小于0 相当于就在头节点插入 
				index = 0;
			}
			LinkedList* newHead = new LinkedList(val);
			LinkedList* cur = _dummy;
			while(index--){
				cur = cur -> next;
			} 
			newHead -> next = cur -> next;
			cur -> next = newHead;
			_size++;//易错点,非常容易忘记对于_size的操作 
		}
		
		//deleteAtIndex(index)：如果索引 index 有效，
		//则删除链表中的第 index 个节点。
		void deleteAtIndex(int index) {
			if(index > (_size - 1) || index < 0){
				return;
			} 
			LinkedList* cur = _dummy;
			while(index--){
				cur = cur -> next;
			}
			//先获取需要删除节点的前一个节点 ,才可以删除 
			LinkedList* temp = cur -> next;
			cur -> next = cur -> next -> next;
			delete temp;
			_size--;//易错点,非常容易忘记对于_size的操作 
		}
			
	private:
		int _size;
		LinkedList* _dummy;
};
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

4. 算法分析

1. int get(int index)方法：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

2. void addAtHead(int val)

• 时间复杂度：O(1)
• 空间复杂度：O(1)

3. void addAtTail(int val)

• 时间复杂度：O(n)
• 空间复杂度：O(1)

4. void addAtIndex(int index, int val)

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. void deleteAtIndex(int index)

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. 算法坑点

1. 增加(add)、删除(delete)方法逻辑写完后,非常容易忘记对_size的操作。
2. 增加时，可以包含index == 链表的长度_size，这与删除、获取链表值的方法不同（index < 链表的长度_size）
3. 不熟悉C++类实例对象的创建，调用方法。