代码随想录算法训练营Day3 203.移除链表元素，707.设计链表，206.反转链表

目录

203.移除链表元素

707.设计链表

206.反转链表 

203.移除链表元素

  1. class Solution {
  2. public:
  3.     ListNode* removeElements(ListNode* head, int val) {
  4.         //头结点值等于val，删除头结点,注意用的是while，因为我们删了一个头结点，但并不意味着下一个节点不等val(比如第2，第3个如果都等val)
  5.         while(head != NULL && head->val == val){
  6.             ListNode *tmp = head;//设一个临时节点指向头指针，便于删除
  7.             head = head->next;//让头指针指向下一个节点，下一个节点变成头结点
  8.             delete tmp;
  9.         }
  10.  
  11.         //头结点值不等于val
  12.         ListNode* p = head;//让我们创建的指针指向头指针
  13.         while(p!= NULL && p->next != NULL){//循环直到下一个指针为空为止
  14.             if(p->next->val == val){//如果等于了要删除的元素
  15.                 ListNode *tmp = p->next;//设一个临时变量，来记录值等于val的节点，然后释放他
  16.                 p->next = p->next->next;//跨过要删除的那个指针，然后接到下一个去，相当于这里其实涉及了三个节点 
  17.                 delete tmp;//删除该节点
  18.             }else{
  19.                 p = p->next;
  20.             }
  21.         }
  22.         return head;
  23.     }
  24. };

707.设计链表

  1. typedef struct {
  2.     int val;
  3.     struct MyLinkedList* next;
  4. } MyLinkedList;
  5.  
  6. MyLinkedList* myLinkedListCreate() {
  7.     MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  8.     head->next = NULL;
  9.     return head;
  10. }
  11.  
  12. int myLinkedListGet(MyLinkedList* obj, int index) {
  13.     MyLinkedList* cur = obj->next;//obj是头指针，obj->next才是首节点
  14.     for (int i = 0; cur != NULL; i++) {//因为index是下标所以不用-1之类的
  15.         if (i == index) {
  16.             return cur->val;
  17.         } else {
  18.             cur = cur->next;
  19.         }
  20.     }
  21.     return -1;
  22. }
  23.  
  24. void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
  25.     MyLinkedList* nhead = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  26.     nhead->val = val;
  27.     nhead->next = obj->next;
  28.     obj->next = nhead;
  29. }
  30.  
  31. void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
  32.     MyLinkedList* cur = obj;
  33.     while (cur->next != NULL) {
  34.         cur = cur->next;
  35.     }
  36.     MyLinkedList* ntail = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  37.     ntail->val = val;
  38.     ntail->next = NULL;
  39.     cur->next = ntail;
  40. }
  41.  
  42. void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
  43.     if (index == 0) {
  44.         myLinkedListAddAtHead(obj, val);
  45.         return;
  46.     }
  47.     MyLinkedList* cur = obj->next;
  48.     for (int i = 1; cur != NULL; i++) {
  49.         if (i == index) {
  50.             MyLinkedList* newnode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  51.             newnode->val = val;
  52.             newnode->next = cur->next;
  53.             cur->next = newnode;
  54.             return;
  55.         } else {
  56.             cur = cur->next;
  57.         }
  58.     }
  59. }
  60.  
  61. void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
  62.     if (index == 0) {
  63.         MyLinkedList* tmp = obj->next;
  64.         if (tmp != NULL) {
  65.             obj->next = tmp->next;
  66.             free(tmp);
  67.         }
  68.         return;
  69.     }
  70.     MyLinkedList* cur = obj->next;
  71.     for (int i = 1; cur != NULL && cur->next != NULL; i++) {
  72.         if (i == index) {
  73.             MyLinkedList* tmp = cur->next;
  74.             if (tmp != NULL) {
  75.                 cur->next = tmp->next;
  76.                 free(tmp);
  77.             }
  78.             return;
  79.         } else {
  80.             cur = cur->next;
  81.         }
  82.     }
  83. }
  84.  
  85. void myLinkedListFree(MyLinkedList* obj) {
  86.     while (obj != NULL) {
  87.         MyLinkedList* tmp = obj;
  88.         obj = obj->next;
  89.         free(tmp);
  90.     }
  91. }

206.反转链表 

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         ListNode* fast = head;//从先去把这个链表遍历一遍到最后，取到最后的位置
  5.         ListNode* slow = head;//指向头指针和快指针进行交换
  6.         int tmp;//用来临时存储val值，交换用的
  7.         int cnt = 0;//负责记录链表长度，然后算出移动次数
  8.         int quanShu = 0;//圈数
  9.         int num = 0;
  10.         int n = 0;
  11.  
  12.         if(fast == nullptr) return head;
  13.  
  14.         while(fast != nullptr){//判断下一个数是不是空的
  15.             fast = fast->next;
  16.             cnt++;
  17.         }
  18.  
  19.         fast = slow;
  20.         quanShu = cnt / 2;//现在的cnt就是圈数了
  21.  
  22.         while((quanShu--) > 0){//交换数值
  23.             for(int i = num; i < cnt-1; i++){
  24.                 fast = fast->next;
  25.             }
  26.                 //快指针移动完之后，开始交换值
  27.                 tmp = fast->val;
  28.                 fast->val = slow->val;
  29.                 slow->val = tmp;
  30.  
  31.                 slow = slow->next;//慢指针前移
  32.                 fast = slow;//重置快指针的位置
  33.                 cnt--;
  34.                 num++;
  35.         }
  36.  
  37.         return head;
  38.     }
  39. };

目录

203.移除链表元素

707.设计链表

206.反转链表 

203.移除链表元素

  1. class Solution {
  2. public:
  3.     ListNode* removeElements(ListNode* head, int val) {
  4.         //头结点值等于val，删除头结点,注意用的是while，因为我们删了一个头结点，但并不意味着下一个节点不等val(比如第2，第3个如果都等val)
  5.         while(head != NULL && head->val == val){
  6.             ListNode *tmp = head;//设一个临时节点指向头指针，便于删除
  7.             head = head->next;//让头指针指向下一个节点，下一个节点变成头结点
  8.             delete tmp;
  9.         }
  10.  
  11.         //头结点值不等于val
  12.         ListNode* p = head;//让我们创建的指针指向头指针
  13.         while(p!= NULL && p->next != NULL){//循环直到下一个指针为空为止
  14.             if(p->next->val == val){//如果等于了要删除的元素
  15.                 ListNode *tmp = p->next;//设一个临时变量，来记录值等于val的节点，然后释放他
  16.                 p->next = p->next->next;//跨过要删除的那个指针，然后接到下一个去，相当于这里其实涉及了三个节点 
  17.                 delete tmp;//删除该节点
  18.             }else{
  19.                 p = p->next;
  20.             }
  21.         }
  22.         return head;
  23.     }
  24. };

707.设计链表

  1. typedef struct {
  2.     int val;
  3.     struct MyLinkedList* next;
  4. } MyLinkedList;
  5.  
  6. MyLinkedList* myLinkedListCreate() {
  7.     MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  8.     head->next = NULL;
  9.     return head;
  10. }
  11.  
  12. int myLinkedListGet(MyLinkedList* obj, int index) {
  13.     MyLinkedList* cur = obj->next;//obj是头指针，obj->next才是首节点
  14.     for (int i = 0; cur != NULL; i++) {//因为index是下标所以不用-1之类的
  15.         if (i == index) {
  16.             return cur->val;
  17.         } else {
  18.             cur = cur->next;
  19.         }
  20.     }
  21.     return -1;
  22. }
  23.  
  24. void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
  25.     MyLinkedList* nhead = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  26.     nhead->val = val;
  27.     nhead->next = obj->next;
  28.     obj->next = nhead;
  29. }
  30.  
  31. void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
  32.     MyLinkedList* cur = obj;
  33.     while (cur->next != NULL) {
  34.         cur = cur->next;
  35.     }
  36.     MyLinkedList* ntail = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  37.     ntail->val = val;
  38.     ntail->next = NULL;
  39.     cur->next = ntail;
  40. }
  41.  
  42. void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
  43.     if (index == 0) {
  44.         myLinkedListAddAtHead(obj, val);
  45.         return;
  46.     }
  47.     MyLinkedList* cur = obj->next;
  48.     for (int i = 1; cur != NULL; i++) {
  49.         if (i == index) {
  50.             MyLinkedList* newnode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
  51.             newnode->val = val;
  52.             newnode->next = cur->next;
  53.             cur->next = newnode;
  54.             return;
  55.         } else {
  56.             cur = cur->next;
  57.         }
  58.     }
  59. }
  60.  
  61. void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
  62.     if (index == 0) {
  63.         MyLinkedList* tmp = obj->next;
  64.         if (tmp != NULL) {
  65.             obj->next = tmp->next;
  66.             free(tmp);
  67.         }
  68.         return;
  69.     }
  70.     MyLinkedList* cur = obj->next;
  71.     for (int i = 1; cur != NULL && cur->next != NULL; i++) {
  72.         if (i == index) {
  73.             MyLinkedList* tmp = cur->next;
  74.             if (tmp != NULL) {
  75.                 cur->next = tmp->next;
  76.                 free(tmp);
  77.             }
  78.             return;
  79.         } else {
  80.             cur = cur->next;
  81.         }
  82.     }
  83. }
  84.  
  85. void myLinkedListFree(MyLinkedList* obj) {
  86.     while (obj != NULL) {
  87.         MyLinkedList* tmp = obj;
  88.         obj = obj->next;
  89.         free(tmp);
  90.     }
  91. }

206.反转链表 

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         ListNode* fast = head;//从先去把这个链表遍历一遍到最后，取到最后的位置
  5.         ListNode* slow = head;//指向头指针和快指针进行交换
  6.         int tmp;//用来临时存储val值，交换用的
  7.         int cnt = 0;//负责记录链表长度，然后算出移动次数
  8.         int quanShu = 0;//圈数
  9.         int num = 0;
  10.         int n = 0;
  11.  
  12.         if(fast == nullptr) return head;
  13.  
  14.         while(fast != nullptr){//判断下一个数是不是空的
  15.             fast = fast->next;
  16.             cnt++;
  17.         }
  18.  
  19.         fast = slow;
  20.         quanShu = cnt / 2;//现在的cnt就是圈数了
  21.  
  22.         while((quanShu--) > 0){//交换数值
  23.             for(int i = num; i < cnt-1; i++){
  24.                 fast = fast->next;
  25.             }
  26.                 //快指针移动完之后，开始交换值
  27.                 tmp = fast->val;
  28.                 fast->val = slow->val;
  29.                 slow->val = tmp;
  30.  
  31.                 slow = slow->next;//慢指针前移
  32.                 fast = slow;//重置快指针的位置
  33.                 cnt--;
  34.                 num++;
  35.         }
  36.  
  37.         return head;
  38.     }
  39. };

注：本文转载自blog.csdn.net的蝶海梦花、的文章"https://blog.csdn.net/m0_74082772/article/details/135874583"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！