PAT甲级备考——链表

• 题目
• • 【1133】链表、链表调整顺序、vector拼接
  • 【1097】链表拆分、合并
  • 【1032】链表判断是否有相同的后缀

PAT (Advanced Level) Practice

【1133】链表、链表调整顺序、vector拼接
【1097】链表拆分、合并
【1074】链表翻转（）
【1052】链表遍历+排序（）
【1032】链表判断是否有相同的后缀

1133 Splitting A Linked List (25 分)
（1）将节点按照顺序保存在vector中，根据每个结点的address和它下一个节点的地址next
（2）vector拼接
（3）注意最后遍历的是v.size()，不是n！！因为在v.push_back阶段，是将满足条件的点输入到v中，不一定有n个

#include
#include
#include
#include
using namespace std;
struct node{
    int address, data, next;
};
int main(){
    int root, n, k, a, b, c;
    cin>>root>>n>>k;
    unordered_map m;
    vector v, v1, v2, v3;
    // 输入map 节点的address：节点
    for(int i=0; i
        scanf("%d %d %d", &a, &b, &c);
        m[a] = node{a,b,c};
    }
    // 将节点按照顺序保存在v中
    for(; root!=-1; root=m[root].next){
        v.push_back(m[root]);
    }
    
    // 按照条件分别保存在v1, v2, v3中，合并三个vector
    for(int i=0; i
        if(v[i].data>k){
            v1.push_back(v[i]);
        }else if(v[i].data<=k && v[i].data>=0){
            v2.push_back(v[i]);
        }else{
            v3.push_back(v[i]);
        }
    }
    v3.insert(v3.end(),v2.begin(),v2.end());
    v3.insert(v3.end(),v1.begin(),v1.end());
    
    // 输出
    for(int i=0; i
        if(i==n-1) printf("%05d %d -1n", v3[i].address, v3[i].data);
        else printf("%05d %d %05dn", v3[i].address, v3[i].data, v3[i+1].address );
    }
}

#include
#include
#include
#include
using namespace std;
struct node{
    int address, data, next;
//     node* next_node;
};
int main(){
    int root, n, k, a, b, c;
    cin>>root>>n>>k;
    unordered_map m;
    vector v, ans;
    for(int i=0; i
        scanf("%d %d %d", &a, &b, &c);
        m[a] = node{a,b,c};
    }
    for(; root!=-1; root=m[root].next){
        v.push_back(m[root]);
    }
    for(int i=0; i
        if(v[i].data<0)
            ans.push_back(v[i]);
    }
    for(int i=0; i
        if(v[i].data<=k && v[i].data>=0)
           ans.push_back(v[i]);
    }
    for(int i=0; i
        if(v[i].data>k)
            ans.push_back(v[i]);
    }
    for (int i = 0; i < ans.size() - 1; i++)
        printf("%05d %d %05dn", ans[i].address, ans[i].data, ans[i + 1].address);
    printf("%05d %d -1n", ans[ans.size() - 1].address, ans[ans.size() - 1].data);


}

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 100000;
struct node{
    int address, data, next, num = 2*maxn;
};
int main(){
    // 输入
    int root, n, a, b, c, cnt=0;
    cin>>root>>n;
    unordered_map m;
    vector v, tmp;
    unordered_set s;
    for(int i=0; i
        scanf("%d %d %d", &a, &b, &c);
        m[a] = node{a,b,c};
    }
    
    // 将所有的节点拆分成两部分，v和tmp
    for(int i=root; i!=-1; i=m[i].next){
        int value = abs(m[i].data);
        if(s.find(value)==s.end()){
            v.push_back(m[i]);
            cnt++;
        }else{
            tmp.push_back(m[i]);
        }
        s.insert(value);
    }
    
    // v和tmp合并，并输出
    v.insert(v.end(), tmp.begin(), tmp.end());
    for(int i=0; i
        if(i==(cnt-1)||i==v.size()-1){
            printf("%05d %d -1n", v[i].address, v[i].data);
        }else{
            printf("%05d %d %05dn", v[i].address, v[i].data, v[i+1].address);
        }
    }
    
    return 0;
}

#include 
using namespace std;
struct NODE {
    char key;
    int next;
    bool flag;
}node[100000];
int main() {
    int s1, s2, n, a, b;
    scanf("%d%d%d", &s1, &s2, &n);
    char data;
    for(int i = 0; i < n; i++) {
        scanf("%d %c %d", &a, &data, &b);
        node[a] = {data, b, false};
    }
    for(int i = s1; i != -1; i = node[i].next)
    node[i].flag = true;
    for(int i = s2; i != -1; i = node[i].next) {
        if(node[i].flag == true) {
            printf("%05d", i);
            return 0;
        }
    }
    printf("-1");
    return 0; }