代码随想录算法训练营Day3 203.移除链表元素,707.设计链表,206.反转链表
目录
(图片来源网络,侵删)
203.移除链表元素
707.设计链表
206.反转链表
203.移除链表元素
class Solution { public: ListNode* removeElements(ListNode* head, int val) { //头结点值等于val,删除头结点,注意用的是while,因为我们删了一个头结点,但并不意味着下一个节点不等val(比如第2,第3个如果都等val) while(head != NULL && head->val == val){ ListNode *tmp = head;//设一个临时节点指向头指针,便于删除 head = head->next;//让头指针指向下一个节点,下一个节点变成头结点 delete tmp; } //头结点值不等于val ListNode* p = head;//让我们创建的指针指向头指针 while(p!= NULL && p->next != NULL){//循环直到下一个指针为空为止 if(p->next->val == val){//如果等于了要删除的元素 ListNode *tmp = p->next;//设一个临时变量,来记录值等于val的节点,然后释放他 p->next = p->next->next;//跨过要删除的那个指针,然后接到下一个去,相当于这里其实涉及了三个节点 delete tmp;//删除该节点 }else{ p = p->next; } } return head; } };
707.设计链表
typedef struct { int val; struct MyLinkedList* next; } MyLinkedList; MyLinkedList* myLinkedListCreate() { MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList)); head->next = NULL; return head; } int myLinkedListGet(MyLinkedList* obj, int index) { MyLinkedList* cur = obj->next;//obj是头指针,obj->next才是首节点 for (int i = 0; cur != NULL; i++) {//因为index是下标所以不用-1之类的 if (i == index) { return cur->val; } else { cur = cur->next; } } return -1; } void myLinkedListAddAtHead(MyLinkedList* obj, int val) { MyLinkedList* nhead = (MyLinkedList*)malloc(sizeof(MyLinkedList)); nhead->val = val; nhead->next = obj->next; obj->next = nhead; } void myLinkedListAddAtTail(MyLinkedList* obj, int val) { MyLinkedList* cur = obj; while (cur->next != NULL) { cur = cur->next; } MyLinkedList* ntail = (MyLinkedList*)malloc(sizeof(MyLinkedList)); ntail->val = val; ntail->next = NULL; cur->next = ntail; } void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { if (index == 0) { myLinkedListAddAtHead(obj, val); return; } MyLinkedList* cur = obj->next; for (int i = 1; cur != NULL; i++) { if (i == index) { MyLinkedList* newnode = (MyLinkedList*)malloc(sizeof(MyLinkedList)); newnode->val = val; newnode->next = cur->next; cur->next = newnode; return; } else { cur = cur->next; } } } void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { if (index == 0) { MyLinkedList* tmp = obj->next; if (tmp != NULL) { obj->next = tmp->next; free(tmp); } return; } MyLinkedList* cur = obj->next; for (int i = 1; cur != NULL && cur->next != NULL; i++) { if (i == index) { MyLinkedList* tmp = cur->next; if (tmp != NULL) { cur->next = tmp->next; free(tmp); } return; } else { cur = cur->next; } } } void myLinkedListFree(MyLinkedList* obj) { while (obj != NULL) { MyLinkedList* tmp = obj; obj = obj->next; free(tmp); } }
206.反转链表
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* fast = head;//从先去把这个链表遍历一遍到最后,取到最后的位置 ListNode* slow = head;//指向头指针和快指针进行交换 int tmp;//用来临时存储val值,交换用的 int cnt = 0;//负责记录链表长度,然后算出移动次数 int quanShu = 0;//圈数 int num = 0; int n = 0; if(fast == nullptr) return head; while(fast != nullptr){//判断下一个数是不是空的 fast = fast->next; cnt++; } fast = slow; quanShu = cnt / 2;//现在的cnt就是圈数了 while((quanShu--) > 0){//交换数值 for(int i = num; i next; } //快指针移动完之后,开始交换值 tmp = fast->val; fast->val = slow->val; slow->val = tmp; slow = slow->next;//慢指针前移 fast = slow;//重置快指针的位置 cnt--; num++; } return head; } };
(图片来源网络,侵删)
(图片来源网络,侵删)
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。
还没有评论,来说两句吧...