目录

1. LeetCode203.移除链表元素

2. LeetCode21.合并两个有序链表

3. LeetCode206.翻转链表

4. LeetCode707.设计链表

1. LeetCode203.移除链表元素

移除链表元素 

题解：通过两个指针来控制，cur和prev；cur指针去找val，prev在cur找之前都先记录一下cur的位置，如果找到了，有两种情况：

        1. 有可能从最开始就找了val；

        2. 在链表的中间找打了； 

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//定义两个指针，prev用来记录cur，cur去找valListNode* prev = nullptr;ListNode* cur = head;while(cur)//知道cur找到空位置为止{if(cur->val != val)//cur所指向的val和要找的val不等{prev = cur;//记录cur的位置cur = cur->next;//cur向后走}else//找到了，分两种情况{if(cur == head)//1.一开始就找到{head = head->next;cur = head;}else//2.其他位置找到了{prev->next = cur->next;cur = prev->next;}}}return head;}
};

2. LeetCode21.合并两个有序链表

 合并两个有序链表

题解：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr)//如果只有list1为空，应该返回list2{return list2;}if(list2 == nullptr)//如果只有list1为空，应该返回list2{return list1;}ListNode* head, *tail;//定义两个指针，用来维护合并的链表head = tail = new ListNode;while(list1 && list2)//如果一个链表走完了，就退出{    //两个链表的值比较，谁小取谁if(list1->val > list2->val){tail->next = list2;tail = tail->next;list2 = list2->next;}else{tail->next = list1;tail = tail->next;list1 = list1->next;}}tail->next = list1 == nullptr ? list2 : list1;//存在一个链表没走完的情况，判断一下return head->next;}
};

3. LeetCode206.翻转链表

 反转链表

题解：

 

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr){return nullptr;}ListNode* n1 = nullptr;ListNode* n2 = head;ListNode* n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;}
};

4. LeetCode707.设计链表

设计链表 

这部分内容在我的数据结构专栏，有C语言模拟的链表，这里不赘述了 

单链表带头结点：

struct listnode
{int val;listnode* next;listnode(int _val):val(_val), next(nullptr){}
};
class MyLinkedList {
public:MyLinkedList() {this->size = 0;this->head = new listnode(0);}int get(int index) {if(index < 0 || index >= size){return -1;}listnode* cur = head;while(index >= 0){   cur = cur->next;index--;}return cur->val;}void addAtHead(int val) {addAtIndex(0, val);}void addAtTail(int val) {addAtIndex(size, val);}void addAtIndex(int index, int val) {if(index > size) return;index = max(0, index);listnode* cur = head;while(index > 0){cur = cur->next;index--;}listnode* newnode = new listnode(val);newnode->next = cur->next;cur->next = newnode;size++;}void deleteAtIndex(int index) {if(index < 0 || index >= size) return;listnode* cur = head;while(index > 0){cur = cur->next;index--;}listnode* prev = cur->next;cur->next = cur->next->next;delete prev;size--;}
private:int size;listnode* head;
};

单链表不带头结点：

struct listnode
{int val;listnode* next;listnode(int _val):val(_val), next(nullptr){}
};
class MyLinkedList {
public:MyLinkedList() {this->size = 0;this->head = nullptr;}int get(int index) {if(index < 0 || index >= size){return -1;}listnode* cur = head;while(index > 0){cur = cur->next;index--;}return cur->val;}void addAtHead(int val) {addAtIndex(0, val);}void addAtTail(int val) {addAtIndex(size, val);}void addAtIndex(int index, int val) {if(index > size) return;listnode* newnode = new listnode(val);if(index == 0){newnode->next = head;head = newnode;}else{listnode* cur = head;listnode* prev = nullptr;while(index > 0){prev = cur;cur = cur->next;index--;}newnode->next = cur;prev->next = newnode; }size++;}void deleteAtIndex(int index) {if(index < 0 || index >= size){return;}if(index == 0 || head->next == nullptr){listnode* cur = head->next;delete head;head = cur;}else{listnode* cur = head;listnode* prev = nullptr;while(index > 0){prev = cur;cur = cur->next;index--;}prev->next = cur->next;delete cur;}size--;}
private:int size;listnode* head;
};