【C语言】初阶数据结构相关习题（二）

🎆个人主页：夜晚中的人海

今日语录：知识是从刻苦劳动中得来的，任何成就都是刻苦劳动的结果。——宋庆龄

文章目录

• 🎄一、链表内指定区间翻转
• 🎉二、从链表中删去总和值为零的节点
• 🚀三、链表求和
• 🏝️四、括号的最大嵌套深度
• 🚘五、整理字符串
• 🏖️六、从根到叶的二进制数之和
• ⭐七、二叉树的坡度

  🎄一、链表内指定区间翻转

  题目描述：链表内指定区间翻转

  

  解题思路：

  1.首先处理特殊情况，如果m == n 时，说明反转的区间只有一个节点，无需进行任何操作，直接返回原链表的头节点 head。

  2.创建一个虚拟头节点 ret，并将其 next 指针指向链表的头节点 head。

  （虚拟头节点的作用是简化边界情况的处理，例如当反转区间包括头节点时，可以避免复杂的头插操作。）

  3.使用两个指针 pm 和 pn。pn 用于定位反转区间的前一个节点，pm 用于定位反转区间的起始节点。

  4.通过第一个for循环，可以将pm指向第m个节点，pn指向第m - 1个节点。

  5.再通过使用第二个 for 循环，从第 m 个节点开始，逐个反转节点，直到第 n 个节点。

  6.最后返回虚拟头结点的下一个节点即（ret -> next）即反转后的链表的头节点。

  代码实现：

  struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) 
  {
      struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
      ret->next = head;
      struct ListNode* pm = ret;
      struct ListNode* pn = head;
      if(m == n)
      {
          return head;
      }
      for(int i = 0;i next;
      }
      for(int i = m;i next;
          pm->next = mid->next;
          mid->next = pn->next;
          pn->next = mid;
      }
      return ret->next;
  }
  

  🎉二、从链表中删去总和值为零的节点

  题目描述：从链表中删去总和值为零的节点

  

  解题思路：

  1.首先创建一个虚拟头节点 ret，并将其 next 指针指向链表的头节点 head。

  2.使用一个指针 prev 从虚拟头节点开始遍历链表。

  （prev 的作用是记录当前需要检查的子链表的起始节点的前一个节点）

  3.使用两个循环，外层循环用于遍历链表，内层循环负责检查子链表的和是否为0。

  4.两层循环都结束后，返回虚拟头节点 ret 的下一个节点（ret->next），即处理后的链表的头节点。

  代码实现：

  struct ListNode* removeZeroSumSublists(struct ListNode* head) {
      struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
      ret->next = head;
      struct ListNode* prev = ret;
      while(prev)
      {
          int sum = 0;
          //内部计算结果
          struct ListNode* cur = prev->next;
          while(cur)
          {
              sum -= cur->val;
              if(sum == 0)
              {
                  prev->next = cur->next;
              }
              cur = cur->next;
          }
          prev = prev->next;
      }
      return ret->next;
  }
  

  🚀三、链表求和

  题目描述：链表求和

  解题思路：

  1.检查输入是否合法，如果l1和l2都为空，那么直接返回0。

  2.创建一个虚拟头节点 dummy，并初始化一个指针 cur 指向虚拟头节点。使用变量 count 表示进位。

  3.使用 while 循环遍历两个链表，直到两个链表都为空。

  4.在每次循环中，获取当前节点的值，创建一个新的节点 newnode，其值为 data，并将其连接到结果链表中。

  5.如果l1不为空或者l2不为空，则还需进行判断，直到两个链表都为空时。

  6.如果循环结束后，count 不为 0，说明还有进位需要处理。创建一个新的节点，其值为 count，并将其连接到结果链表的末尾。

  代码实现：

  struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
      if(l1 && l2 == NULL)
      {
          return 0;
      }
      struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
      struct ListNode* cur = dummy;
      //进位
      int count = 0;
      while(l1 || l2)
      {
          int val1 = (l1?l1->val:0);
          int val2 = (l2?l2->val:0);
          int sum = val1 + val2 + count;
          //获取个位
          int data = sum % 10;
          count = sum / 10;
          struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
          newnode->val = data;
          newnode->next = NULL;
          cur->next = newnode;
          cur = cur->next;
          if(l1)
          {
              l1 = l1->next;
          }
          if(l2)
          {
              l2 = l2->next;
          }
      }
      if(count)
      {
          struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
          newnode->val = count;
          newnode->next = NULL;
          cur->next = newnode;
      }
      return dummy->next;
  }
  

  🏝️四、括号的最大嵌套深度

  题目描述：括号的最大嵌套深度

  

  解题思路：

  1.首先创建三个变量：top用于记录当前括号的嵌套层数；count用于记录最大的嵌套深度；i用于遍历字符串的索引。

  2.使用 while 循环遍历字符串，直到遇到字符串的结束符 ‘\0’。

  3.遇到左括号时，top+1，使用fmax函数更新count，确保count始终处于记录最大嵌套的深度。

  4.遇到右括号时，top–。

  5.循环结束后，返回count即代表最大的嵌套深度。

  代码实现：

  int maxDepth(char* s) {
      int top = 0;
      int count = 0;
      int i = 0;
      while(s[i] != '\0')
      {
          if(s[i] == '(')
          {
              top++;
              count = fmax(top,count);
          }
          else if(s[i] == ')')
          {
              top--;
          }
          i++;
      }
      return count;
  }
  

  🚘五、整理字符串

  题目描述：整理字符串

  

  解题思路：

  1.首先创建三个变量，i用于遍历字符串的索引；len表示字符串的长度；top用于模拟栈的栈顶指针，初始值为-1，表示栈为空。

  2.使用一个循环遍历字符串，每次将当前字符放入栈中。

  3.检查栈顶的两个字符是否满足相邻且大小写不同的条件，如果满足则移除这两个字符，否则继续处理下一个字符。

  4.循环结束后，栈中剩余的字符即为结果。

  代码实现：

  char* makeGood(char* s) {
      int i = 0;
      int len = strlen(s);
      int top = -1;
      for(i = 0;i
          s[++top] = s[i];
          if(top  0)
          {
              if(abs(s[top] - s[top - 1]) == 'a' - 'A')
              {
                  top -= 2;
              }
          }
      }
      s[top + 1] = '\0';
      return s;
  }
  

  🏖️六、从根到叶的二进制数之和

  题目描述：从根到叶的二进制数之和

  

  解题思路：

  1.首先处理特殊情况，如果当前节点为空，则返回0，表示没有路径。

  2.若节点不为空，则将当前节点的值加入路径的二进制表示中。

  3.如果当前节点是叶子节点，则返回当前路径的二进制值val。

  4.如果当前节点不是叶子节点，递归计算左子树和右子树的路径和，并将结果相加。

  5.最后在主函数中调用Count，从根节点开始，初始路径值为0。

  代码实现：

  //计算左右路径之和
  int Count(struct TreeNode* root,int val)
  {
      if(root == NULL)
      {
          return 0;
      }
      val = (valleft == NULL && root->right == NULL)
      {
          return val;
      }
      return Count(root->left,val) + Count(root->right,val);
  }
  int sumRootToLeaf(struct TreeNode* root) {
      return Count(root,0);
  }
  

  ⭐七、二叉树的坡度

  题目描述：二叉树的坡度

  

  解题思路：

  1.使用一个辅助函数Count，用于计算以 root 为根的子树的所有节点值之和。

  2.在使用一个辅助函数prevOrder，用于通过前序遍历计算整棵树的坡度，并将结果累加到 sum 中。

  3.最后在主函数中定义一个变量ret，表示整棵树的坡度，通过调用prevOrder函数，从根节点开始计算整棵树的倾斜度。

  4.最后返回坡度ret即可。

  代码实现：

  int Count(struct TreeNode* root)
  {
      if(root == NULL)
      {
          return 0;
      }
      return Count(root->left) + Count(root->right) + root->val;
  }
  void prevOrder(struct TreeNode* root,int* sum)
  {
      if(root == NULL)
      {
          return;
      }
      int left = Count(root->left);
      int right = Count(root->right);
      (*sum) += abs(left - right);
      prevOrder(root->left,sum);
      prevOrder(root->right,sum);
  }
  int findTilt(struct TreeNode* root) {
      int ret = 0;
      prevOrder(root,&ret);
      return ret;
  }
  

  今天的分享就到这里啦，如果感到不错，希望能给博主一键三连，感谢大家的支持！希望这篇文章可以帮到大家，我们下期再见！