707. 设计链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 332 阅读时长 ≈ 1 分钟

考点

  • 链表的常用操作设计

题解

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
class MyLinkedList {
	private:
		int size;
		ListNode *dummyHead;
	public:
		MyLinkedList() : size(0), dummyHead(new ListNode(-1)) {}

		int get(int index) {
			if (index < 0 || index > size - 1) return -1;
			ListNode *cur = dummyHead->next;
			while (index--)	cur = cur->next;
			return cur->val;
		}

		void addAtHead(int val) {
			dummyHead->next = new ListNode(val, dummyHead->next);
			size++;
		}

		void addAtTail(int val) {
			ListNode *cur = dummyHead;
			while (cur->next != nullptr) cur = cur->next;
			cur->next = new ListNode(val, nullptr);
			size++;
		}

		void addAtIndex(int index, int val) {
			if (index > size) return;
			ListNode *cur = dummyHead;
			while (index--) cur = cur->next;
			cur->next = new ListNode(val, cur->next);
			size++;
		}

		void deleteAtIndex(int index) {
			if (index < 0 || index > size - 1) return;
			ListNode *cur = dummyHead;
			while (index--) cur = cur->next;
			ListNode *tmp = cur->next;
			cur->next = cur->next->next;
			delete tmp;
			size--;
		}
};

思路

题目较为简单，具体实现见代码即可；主要讲几个细节：

  1. 链表类的题基本都需要新增一个dummyHead伪节点，指向真正的头节点；以避免考虑操作头节点时的特殊情况

  2. 单链表类的题涉及迭代操作某一节点时，都应定位到该节点的前一节点；因为若不修改前一节点的next信息，新链表串不起来

    （使用递归或双向链表就可以自由发挥了）

    比如需要删除节点3，我们需要定位到节点2

    待处理完节点3后，需要将节点2与节点4连接起来，链表才是完整的