代码随想录day03 203.移除链表元素 707.设计链表 206.反转链表

链表

203. 移除链表元素

基础题，没啥难度

class Solution {
public:

void deleteNextListNode(ListNode *pre) {
    if (pre == NULL || pre->next == NULL) return;
    ListNode *tmp = pre->next;
    pre->next = tmp->next;
    delete tmp;
}

ListNode *removeElements(ListNode *head, int val) {
    ListNode *dummyNode = new ListNode(0, head);
    ListNode *pre = dummyNode;
    while (pre->next != NULL) {
        if (pre->next->val == val) {
            deleteNextListNode(pre);
            continue;
        }
        pre = pre->next;
    }
    return dummyNode->next;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

707. 设计链表

麻烦的题目，不是难，就是麻烦

class MyLinkedList {
public:

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

	MyLinkedList() {
		_dummyNode = new LinkedNode(0);
		_size = 0;
	}

	int isEmpty() {
		return _size == 0;
	}

	int get(int index) {
		LinkedNode *cur = _dummyNode->next;
		int i = 0;
		while (cur != NULL && i < index) {
			cur = cur->next;
			i++;
		}
		if (cur == NULL) return -1;
		return cur->val;
	}

	void addAtHead(int val) {
		LinkedNode *cur = new LinkedNode(val);
		cur->next = _dummyNode->next;
		_dummyNode->next = cur;
		_size++;
	}

	void addAtTail(int val) {
		LinkedNode *pre = _dummyNode;
		while (pre->next != NULL) pre = pre->next;
		LinkedNode *tmp = new LinkedNode(val);
		pre->next = tmp;
		_size++;
	}

	void addAtIndex(int index, int val) {
		LinkedNode *pre = _dummyNode;
		int i = 0;
		while (pre->next != NULL && i < index) {
			pre = pre->next;
			i++;
		}
		if (i != index) return;
		LinkedNode *tmp = new LinkedNode(val);
		tmp->next = pre->next;
		pre->next = tmp;
		_size++;
	}

	void deleteAtIndex(int index) {
        if (_size <= index) return;
		LinkedNode *pre = _dummyNode;
		int i = 0;
		while (pre->next != NULL && i < index) {
			pre = pre->next;
			i++;
		}
		LinkedNode *tmp = pre->next;
		pre->next = tmp->next;
		delete tmp;
		tmp = NULL;
		_size--;
	}

	void printLinkedList() {
		LinkedNode *cur = _dummyNode->next;
		while (cur != NULL) {
			cout << cur->val;
			cur = cur->next;
			if (cur != NULL) cout << "->";
		}
		cout << endl;
	}

private:
	LinkedNode *_dummyNode;
	int _size;
};
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

206. 反转链表

设置好三个指针的位置就能秒

class Solution {
public:
ListNode *reverseList(ListNode *head) {
    ListNode *pre = nullptr;
    ListNode *cur = head;
    ListNode *next;
    while (cur != nullptr)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16