PAT 1052. Linked List Sorting
2024-08-24 01:50:52
这场考试当年还参加了，当时直接用内置的排序了，否则自己写归并排序浪费时间啊，现在来练习一发。估计又有些节点没在链表里面，当时没考虑这个情况，所以一直有些case没过
#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map> using namespace std; class Node {
public:
int data;
int next;
Node() : data(), next(-){
cout<<"should not happend"<<endl;
}
Node(int d, int n) : data(d), next(n) {}
}; int count(int head, unordered_map<int, Node>& mem) {
int cur = head;
int cnt = ;
while (cur != -) {
cnt++;
cur = mem[cur].next;
}
return cnt; } int step(int head, int k, unordered_map<int, Node>& mem) {
int cur = head;
while (cur != -) {
if (k-- == ) {
break; }
cur = mem[cur].next;
}
return cur;
} int merge_list(int heada, int headb, unordered_map<int, Node>& mem) {
int nhead = -;
int last = -;
int select = -;
int ca = heada, cb = headb;
while (ca != - && cb != -) {
Node& na = mem[ca];
Node& nb = mem[cb]; if (na.data > nb.data) {
select = cb;
cb = nb.next;
} else if (na.data <= nb.data) {
select = ca;
ca = na.next;
} if (last == -) {
nhead = select;
} else {
mem[last].next = select;
}
last = select;
} int last_part = -; if (ca != -) {
last_part = ca;
} if (cb != -) {
last_part = cb;
} if (last == -) {
nhead = last_part;
} else {
mem[last].next = last_part;
} return nhead;
} int sort_list(int head, int n, unordered_map<int, Node>& mem) { if (n < ) {
return -;
} if (n == ) {
mem[head].next = -;
return head;
} int a_cnt = n / ;
int b_cnt = n - a_cnt; int ca = head;
int cb = step(head, a_cnt, mem); ca = sort_list(ca, a_cnt, mem);
cb = sort_list(cb, b_cnt, mem); return merge_list(ca, cb, mem); } void print_list(int head, unordered_map<int, Node>& mem) {
int cur = head;
while (cur != -) {
Node& cn = mem[cur];
if (cn.next == -) {
printf("%05d %d %d\n", cur, cn.data, cn.next);
} else {
printf("%05d %d %05d\n", cur, cn.data, cn.next);
}
cur = mem[cur].next;
}
} int main() { int N, head; scanf("%d%d", &N, &head); unordered_map<int, Node> mem; for (int i=; i<N; i++) {
int addr, data, next;
scanf("%d%d%d", &addr, &data, &next);
mem.insert(make_pair(addr, Node(data, next)));
} int n = count(head, mem); head = sort_list(head, n, mem);
if (n > ) {
printf("%d %05d\n", n, head);
} else {
printf("%d %d\n", n, head);
}
print_list(head, mem); return ; }
最新文章
- Python3.5 day3作业一：实现简单的shell sed替换功能
- Matches正则使用提取内容
- [SQL入门级] 上篇被移出园子首页，那这篇咱就'薄利多销'
- 有效解决 iOS The document “(null)” requires Xcode 8.0 or later.
- PHP基础之 数组（二）
- jq选中问题
- Scala access modifiers and qualifiers in detail
- 只有图片拼接的html页面图片之间有白条的解决方法
- POJ 1258 Agri-Net（最小生成树，基础）
- [ACM] 最短路算法整理（bellman_ford , SPFA , floyed , dijkstra 思想，步骤及模板）
- hadoop学习记录（零）
- 什么时候PHP经验MySQL存储过程
- php使用select语句查询数据信息
- Hello Flask
- Vue+Vue-router微信分享功能
- Windows系统环境下创建mysql主从数据库方法（双向主从复制）
- .Net拾忆：Asp.net请求管道
- DNS 基础
- PHP: Short URL Algorithm Implementation
- 如何更换Office 2013的product key?