目录
一、LeetCode 203移除链表元素
二、LeetCode707设计链表
三、LeetCode206反转链表
一、LeetCode 203移除链表元素
题目链接：. - 力扣（LeetCode）
题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路：
与传统的链表的增删改查不同的是，力扣中链表的头结点是第一个结点，这与我们之前讲述的头结点、首元结点不同，所以我们这个题主要考虑的点在于，头结点如果被删除了怎么办？
所以我们有两种做法：
1、直接使用原来的链表进行删除操作（需要判断头结点有没有被删除）；
2、设置一个虚拟头结点再进行删除操作。
方法一：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* temp;
//判断头结点是不是被删除的结点while(head && head->val==val)//如果是，删除第一个结点，让头结点后移{temp=head;head=head->next;free(temp);}//判断其他节点是不是被删除的结点struct ListNode *cur =head;while(cur && (temp=cur->next)){if(temp->val==val)//判断是否需要删除{cur->next=temp->next;free(temp);}elsecur=cur->next;} return head;
}方法二：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {
//构建一个虚拟头结点，并让其next指针指向头结点struct ListNode* temp=(struct ListNode* )malloc(sizeof( struct ListNode));temp->next=head;struct ListNode* cur=temp;
//判断指针指向的是不是最后一个节点while(cur->next){if(cur->next->val==val)//判断指针指向的结点的值与判断的值是否一致{//一致，准备删除节点struct ListNode* tep=cur->next;cur->next=tep->next;free(tep);}else{//不一致，指针指向后一个节点cur=cur->next;}}head = temp->next;//防止头结点被删除，就不能直接返回headfree(temp);return head;
}二、LeetCode707设计链表
题目链接：. - 力扣（LeetCode）
题目描述：
你可以选择使用单链表或者双链表，设计并实现自己的链表。单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
思路：
本题考察的内容，其实就是链表的增删查等操作，所以我们还是最好能构建一个虚拟头结点。
需要注意的是：
1、虚拟头结点的创建；
2、index是从0开始还是从1开始；
3、在删除、增加等操作时，需要注意确定的位置应该是index前面的一个位置；
4、在查找的时候，确定的位置应该是index的位置。
typedef struct {int val;struct MyLinkedList* next;
} MyLinkedList;MyLinkedList* myLinkedListCreate() {MyLinkedList *obj=( MyLinkedList*)malloc(sizeof( MyLinkedList));obj->val=0;obj->next=NULL;return obj;
}int myLinkedListGet(MyLinkedList* obj, int index) {while(index<0||index>=obj->val)return -1;MyLinkedList *cur=obj->next;while(index--){cur=cur->next;}return cur->val;
}void myLinkedListAddAtHead(MyLinkedList* obj, int val) {MyLinkedList *node=( MyLinkedList*)malloc(sizeof( MyLinkedList));node->val=val;node->next=obj->next;obj->next=node;obj->val++;
}void myLinkedListAddAtTail(MyLinkedList* obj, int val) {MyLinkedList *node=( MyLinkedList*)malloc(sizeof( MyLinkedList));node->val=val;MyLinkedList *cur=obj;while(cur->next){cur=cur->next;}node->next=cur->next;cur->next=node;obj->val++;
}void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {while(index<0||index>obj->val)return ;MyLinkedList *node=(MyLinkedList*)malloc(sizeof( MyLinkedList));node->val=val;MyLinkedList *cur=obj;while(index--){cur=cur->next;}node->next=cur->next;cur->next=node;obj->val++;
}void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {while(index<0|index>=obj->val)return;MyLinkedList *cur=obj;while(index--){cur=cur->next;}MyLinkedList *temp=cur->next;cur->next=temp->next;free(temp);obj->val--;
}void myLinkedListFree(MyLinkedList* obj) {MyLinkedList *cur=obj->next;while(cur){MyLinkedList *temp=cur;cur=cur->next;free(temp);}free(obj);
}/*** Your MyLinkedList struct will be instantiated and called as such:* MyLinkedList* obj = myLinkedListCreate();* int param_1 = myLinkedListGet(obj, index);* myLinkedListAddAtHead(obj, val);* myLinkedListAddAtTail(obj, val);* myLinkedListAddAtIndex(obj, index, val);* myLinkedListDeleteAtIndex(obj, index);* myLinkedListFree(obj);
*/三、LeetCode206反转链表
题目链接：. - 力扣（LeetCode）
题目描述： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路：采用双指针的做法，关键在于将反转前的位置进行保存，如果只用一个指针，反转之后就找不到链表连接的位置。
代码实现：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {//创建pre，，指向当前结点的前一个节点struct ListNode* pre;pre=(struct ListNode*)malloc(sizeof(struct ListNode));pre=NULL;while(head){struct ListNode* temp=head->next;//保存下一个节点的位置head->next=pre;//翻转操作pre=head;//更新结点head=temp;}return pre;
}
