如何申请一个网站 做视频直播,网站建设自学视频,wordpress网站搬家换域名,湖南网站seo优化题目描述
给定一个单链表 L#xff0c;请编写程序输出 L 中间结点保存的数据。
如果有两个中间结点#xff0c;则输出第二个中间结点保存的数据。例如#xff1a;
给定 L 为 1→7→5#xff0c;则输出应该为7#xff1b; 给定 L 为 1→2→3→4#xff0c;则输出应该为…题目描述
给定一个单链表 L请编写程序输出 L 中间结点保存的数据。
如果有两个中间结点则输出第二个中间结点保存的数据。例如
给定 L 为 1→7→5则输出应该为7 给定 L 为 1→2→3→4则输出应该为3 输入描述 每个输入包含1个测试用例。
每个测试用例
第一行给出链表首结点的地址、结点总个数正整数 N ≤ 10^5。结点的地址是5位非负整数NULL地址用-1表示。
接下来有N行每行格式位
Address Data Next
其中Address是结点地址Data是该结点保存的整数数据0 ≤ Data ≤ 10^8Next是下一结点的地址。
输出描述
对每个测试用例在一行中输出 L 中间结点保存的数据。 如果有两个中间结点则输出第二个中间结点保存的数据。
用例1 输入 00010 4 00000 3 -1 00010 5 12309 11451 6 00000 12309 7 11451 输出 6 用例2 输入 10000 3 76892 7 12309 12309 5 -1 10000 1 76892 输出 7
解析
为了解决这个问题我们可以使用快慢指针的方法。快指针每次移动两步慢指针每次移动一步。当快指针到达链表末尾时慢指针将位于链表的中间。如果链表长度是奇数则慢指针指向的就是中间节点如果链表长度是偶数则慢指针指向的是中间两个节点中的第一个但因为我们要求输出第二个中间节点所以在这种情况下我们还需要额外处理一次。
以下是具体的算法步骤
初始化两个指针slow 和 fast都指向链表的头结点。 进入循环在循环中fast 每次移动两步slow 每次移动一步。如果 fast 或 fast-next 为 NULL则跳出循环。 如果链表长度是偶数且 fast 为 NULL那么 slow 指向的是中间两个节点中的第一个我们需要将 slow 移动到下一个节点。 输出 slow 指向的节点的数据。 现在我们根据上述步骤来实现具体的代码。注意因为输入是通过文本格式给出的我们首先需要解析输入以构建链表然后再执行上述算法。
以下是一个可能的C实现
#include iostream
#include unordered_map
using namespace std; struct ListNode { int address; int data; int next; ListNode(int a, int d, int n) : address(a), data(d), next(n) {}
}; unordered_mapint, ListNode* addressToNode; int main() { int headAddress, N; cin headAddress N; // 读取链表信息并构建链表 for (int i 0; i N; i) { int a, d, n; cin a d n; addressToNode[a] new ListNode(a, d, n); } ListNode* head addressToNode[headAddress]; ListNode* slow head; ListNode* fast head; // 快慢指针寻找中间节点 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } // 如果链表长度是偶数且fast为NULL则slow指向的是中间两个节点中的第一个 // 因此我们需要将slow移动到下一个节点 if (fast nullptr) { slow slow-next; } // 输出中间节点的数据 cout slow-data endl; // 释放链表内存 for (auto pair : addressToNode) { delete pair.second; } return 0;
}注意上述代码假设输入的链表数据是合法的没有进行错误处理。在实际应用中你可能需要添加额外的错误处理代码来确保程序的健壮性。此外这段代码使用了C的STL库中的unordered_map来方便地通过地址查找节点。
代码
为了解决这个问题我们需要先定义链表节点的数据结构然后编写程序来构建链表并找到中间节点。由于每个语言的实现细节略有不同我将分别为Java、JavaScript、Python、C和C提供解决方案。
Java Java中没有直接支持链表的地址操作但我们可以模拟这个过程使用整数作为地址并构建链表。
java
import java.util.*; class ListNode { int address; int data; int next; ListNode(int address, int data, int next) { this.address address; this.data data; this.next next; }
} public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取首节点地址和节点总数 int headAddress scanner.nextInt(); int n scanner.nextInt(); MapInteger, ListNode nodeMap new HashMap(); // 读取节点信息 for (int i 0; i n; i) { int address scanner.nextInt(); int data scanner.nextInt(); int next scanner.nextInt(); ListNode node new ListNode(address, data, next); nodeMap.put(address, node); } // 构建链表 ListNode head nodeMap.get(headAddress); ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 输出中间节点的数据 System.out.println(slow.data); scanner.close(); }
}JavaScript 在JavaScript中我们可以使用对象来模拟链表节点并构建链表。
javascript
const readline require(readline);
const rl readline.createInterface({ input: process.stdin, output: process.stdout
}); class ListNode { constructor(address, data, next) { this.address address; this.data data; this.next next; }
} rl.on(line, (line) { const [headAddress, n] line.split( ).map(Number); const nodeMap {}; for (let i 0; i n; i) { const [address, data, next] rl.readLine().sync().split( ).map(Number); nodeMap[address] new ListNode(address, data, next); } let head nodeMap[headAddress]; let slow head, fast head; while (fast fast.next) { slow slow.next; fast fast.next.next; } console.log(slow.data); rl.close();
});Python 在Python中我们可以使用字典来模拟链表节点的地址映射并构建链表。
python
class ListNode: def __init__(self, address, data, next): self.address address self.data data self.next next def find_middle_node(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow.data if __name__ __main__: n, head_address map(int, input().split()) nodes {} for _ in range(n): address, data, next_address map(int, input().split()) nodes[address] ListNode(address, data, next_address) head nodes[head_address] middle_data find_middle_node(head) print(middle_data)C 在C语言中我们可以使用结构体来表示链表节点并使用数组来模拟地址映射。
c
#include stdio.h
#include stdlib.h #define MAX_NODES 100000 typedef struct ListNode { int address; int data; int next;
} ListNode; ListNode nodes[MAX_NODES]; int main() { int headAddress, n
