Leetcode60天刷题第三天链表--移除链表元素，设计链表，反转链表

移除链表元素

题目：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例2：

输入：head = [], val = 1
输出：[]

示例3：

输入：head = [7,7,7,7], val = 7
输出：[]

首先要弄清楚链表的结构，链表是由节点组成，而一个节点包含有一个val和一个指向下一个节点的指针，当我们要移除链表中的节点时，要分以下步骤

1. 创建一个cur指针遍历链表。这里不能用head的原因是要通过返回head来找到该链表，如果用head指针遍历，最后返回的head就不能找到链表了。
2. 创建一个temp指针指向要删除的节点。
3. 通过这个临时指针将要删除节点的前一个节点的next直接指向删除节点的next节点。
4. 删除temp指针。

class Solution{
public:
	ListNode* removeElements(ListNode* head, int val){
		while(head && head->val == val){ //注意这里判断head->val == val要在while循环里，如果放在while循环里用if判断会陷入死循环。
			ListNode* temp = head;
			head = head->next;
			delete temp;	
		}
		ListNode* cur = head;
		while(cur && cur->next){
			if(cur->next->val == val){
				ListNode* temp = cur->next;
				cur->next = temp->next;
				delete temp;
			}else{
				cur = cur->next;
			}
		}
		return head;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第二钟思路是加入虚拟头节点，主要是为了方便移除，不用将头节点分出来讨论了

class Solution{
public:
	ListNode* removeElements(ListNode* head, int val){
		ListNode* _dummyHead = new ListNode(0);
		_dummyHead->next = head;
		ListNode* cur = head;
		while(cur && cur->next){
			if(cur->next->val == val){
				ListNode* temp = cur->next;
				cur->next = temp->next;
				delete temp;
			}else{
				cur = cur->next;	
			}
		}
		return head;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

设计链表

题目：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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

class MyLinkedList{
public:
	struct LinkedNode{
		int val;
		LinkedNode* next;
		LinkedNode(int val):val(val), next(nullptr){};
	};
	
	MyLinkedList(){
		_dummyHead = new LinkedNode(0);
		_size = 0;
	}

	int get(int index){
		if (index < 0 || index > (_size - 1)) return -1;
        LinkedNode* cur = _dummyHead->next;
		while(index--){
			cur = cur->next;	
		}
		return cur->val;
	}

	void addAtHead(int val){
		LinkedNode* newNode  = new LinkedNode(val);
		newNode->next = _dummyHead->next;
		_dummyHead->next = newNode;
		_size++;
	}
    
    // 在链表最后面添加一个节点
	void addAtTail(int val){
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
	}
	
	//如果 index 等于链表的长度，则该节点将附加到链表的末尾。
	//如果 index 大于链表长度，则不会插入节点。
	//如果index小于0，则在头部插入节点。
	void addAtIndex(int index, int val){
		if(index > _size){
			return;
		}else if(index < 0){
			addAtHead(val);
		}else{
			LinkedNode* newNode = new LinkedNode(val);
			LinkedNode* cur = _dummyHead;
			while(index--){
				cur = cur->next;
			}
			newNode->next = cur->next;
			cur->next = newNode;
			_size++;
		}
	}

	void deleteAtIndex(int index){
		if(index < 0 || index >= _size){
            return;
        }
		LinkedNode* cur = _dummyHead;
		while(index--){
			cur = cur-> next;
		}
		LinkedNode* temp = cur->next;
		cur->next = temp->next;
		delete temp;
		_size--;
    }

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

反转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]
输出：[2,1]

示例3：

输入：head = []
输出：[]

双指针法：

1. 创建一个cur指针，用该指针遍历链表，创建一个pre指针指向nullptr。
2. 在cur遍历链表时，用temp指针保存下cur->next的地址，再将cur->next指向pre从而实现翻转链表的效果，然后将pre和cur继续遍历。

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

递归法：双指针思想的递归法

class Solution{
public:
	ListNode* reverse(ListNode* pre, ListNode* cur){
		if(cur == nullptr)return pre;
		ListNode* temp = cur-> next;
		cur->next = pre;
		return reverse(cur, temp); 
    }
		
	ListNode* reverseList(ListNode* head){
		return reverse(nullptr, head);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13