《数据结构与算法C++版第三版》第四章答案 |21xrx.com

《数据结构与算法C++版第三版》第四章答案

2023-07-04 20:37:27 深夜i -- --

数据结构算法 C++版第三版第四章答案

《数据结构与算法C++版第三版》第四章是关于链表的内容，包括单链表、双链表和循环链表等，本章的题目很多，但都是基于链表的基本操作、算法和应用的练习。

下面是本章的部分答案：

1. 实现一个单链表的反转。

答案如下：


void reverse(ListNode *&head) {
  ListNode *prev = nullptr; // 上一个节点
  ListNode *curr = head;  // 当前节点
  ListNode *next = nullptr; // 下一个节点
  while (curr != nullptr)
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  
  head = prev;
}

2. 合并两个有序的单链表。

答案如下：


ListNode* merge(ListNode *l1, ListNode *l2) {
  ListNode *head = new ListNode(0); // 哨兵节点
  ListNode *cur = head; // 当前节点
  while (l1 != nullptr && l2 != nullptr) {
    if (l1->val < l2->val)
      cur->next = l1;
      l1 = l1->next;
     else
      cur->next = l2;
      l2 = l2->next;
    
    cur = cur->next;
  }
  cur->next = (l1 != nullptr) ? l1 : l2;
  return head->next;
}

3. 判断一个链表是否有环路。

答案如下：


bool hasCycle(ListNode *head) {
  ListNode *slow = head;
  ListNode *fast = head;
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast)
      return true;
    
  }
  return false;
}

4. 求一个链表的中间节点。

答案如下：


ListNode* middleNode(ListNode* head) {
  ListNode *slow = head;
  ListNode *fast = head;
  while (fast != nullptr && fast->next != nullptr)
    slow = slow->next;
    fast = fast->next->next;
  
  return slow;
}

本章的练习题都是对链表的基本操作、算法和应用的综合练习，对于提高编程能力和思维能力都有很大的帮助，希望大家可以认真地完成。

上一篇: idea打包java可执行jar包

下一篇: C++中的构造函数是什么意思？

评论区

()

相似文章