707.设计链表

力扣

题意：

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

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

思路

链表的增删查改实现。与之前学的数据结构链表学习不太一样。当时写了链表的创建、删除，认为增加和修改操作大同小异，就没有实践。知道做了这一题，才发现了许多没注意的细节问题。

链表问题，可以用数组、双指针的思路来解决。

​ 数组算是暴力解，先把链表中的值存在数组中，然后按照 规定取出组成新链表。

​ 双指针的话则要注意pre、cur指针，一定要平移，元素的位置不能动。总之，元素和指针只能动一个，不可以两个同时动，否则会被卷入循环漩涡，出不来结果。

​ 做题时一定要画图，把思路写出来，再实现代码，会对代码实现的逻辑有比较清楚的把控，debug的时候容易找出问题所在处。

​ 做题的时候要注意，头节点是否变动！！！（运行完函数后，是否有返回头节点）

以下是C语言实现设计链表：

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
125
typedef struct MyLinkedList{
	int val;
	struct MyLinkedList* next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {//链表创建
	MyLinkedList* L = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	L->next = NULL;
	L->val = 0;
	return L;
}

int myLinkedListGet(MyLinkedList* obj, int index) {//获取下标为index的节点值，没有返回-1
	int cout = 0;
	obj = obj->next;
	while (obj){
		if (index == cout){
			return obj->val;
		}
		obj = obj->next;
		cout++;
	}
	return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {//插入至第一个元素之前
	MyLinkedList* first = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	first->val = val;
	first->next = obj->next;
	obj->next= first;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {//插入至最后一个元素之后
	MyLinkedList* last = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	last->val = val;
	last->next = NULL;
	MyLinkedList* cur;
	cur = obj->next;
    if (cur == NULL) {
		obj->next = last;
	}
	while (cur){
		if (cur->next == NULL){
			cur->next = last;
			break;
		}
		else{
			cur = cur->next;
		}
	}

}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {//将val插入下标index节点之前
	MyLinkedList* mid = (MyLinkedList*)malloc(sizeof(MyLinkedList));//没注意。如果index等于链表长度，则把val加在链表末端
	MyLinkedList* before = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	MyLinkedList* cur;
	MyLinkedList* pre = obj;
	mid->val = val;
	int flag = 1;
	int cout = 0;
	cur = obj->next;
	while (cur){
		if (index == cout)
		{
			pre->next= mid;
			mid->next = cur;
			flag = 0;
			break;
		}
		cout++;//在cur指向NULL的时候，cout还加了1
		pre = cur;
		cur = cur->next;
	}
	if (index == (cout)&&flag){
		pre->next = mid;
		mid->next = NULL;
	}
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {//如果下标有效，删除下标为index的节点
	int cout = 0;
	MyLinkedList* pre = obj;
	MyLinkedList* temp;
	MyLinkedList* cur;
	//temp = obj->next;//第一个元素
	if (index == 0){
		temp = obj->next;
		obj->next = obj->next->next;
		free(temp);
	}
	cur = obj->next;
	if (index !=0 )
	{
		while (cur)
		{
			if (index == cout)
			{
				pre->next = cur->next;
				free(cur);
				break;
			}
			cout++;
			pre = cur;
			cur = cur->next;
		}
	}


	
}

void myLinkedListFree(MyLinkedList* obj) {//释放链表所有元素
	MyLinkedList* cur;
	MyLinkedList* pre;
	cur = obj->next;
	while (cur){
		pre = cur;
		cur = cur->next;
		free(pre);
	}
	pre = obj;
	free(pre);
}