PAT-Advanced LinkedList

2020-04-06
Abstract：简单通过静态链表来处理比较方便，当然也比较费空间，另外输出格式是个坑

1032 Sharing (25分)

image-20200406170958083image-20200406171008546

解法一：标记法

同HashSet法，遍历a链表将所有经过的节点标记一次，再遍历b输出遇到的第一个标记过的节点

#include<iostream>

struct Node {
    int next = -1;
    bool is_visited = false;
} node[100001];

char data;
int num, s1, s2, address;

void parse_input() {
    std::cin >> s1 >> s2 >> num;
    for (int i = 0; i < num; i++) {
        std::cin >> address >> data;
        std::cin >> node[address].next;
    }
}

int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0);
    parse_input();

    for (s1; s1 != -1; s1 = node[s1].next)
        node[s1].is_visited = true;

    for (s2; s2 != -1; s2 = node[s2].next)
        if (node[s2].is_visited) { printf("%05d",s2); return 0; }
    std::cout << -1;
}

解法二：双指针

考虑将两条链合并，即左链结束时链接右链，右链结束时链接左链

此时会出现一种现象：假设左链长n，右链长m，交点在左链的a位置，在右链的b位置，那么就有 m+a = n+b，也就是两个指针会在第二次遍历对方那条链时相遇

#include<iostream>

struct Node {
	char val;
	int next = -1;
} node[100002];

char val;
int address, next, num, s1, s2;

void parse_input() {
	scanf("%d%d%d", &s1, &s2, &num);
	for (int i = 0; i < num; i++) {
		scanf("%d %c %d", &address, &val, &next);
		node[address] = { val,next };
	}
}

int get_intersection(int s1, int s2) {
	int curr_a = s1, curr_b = s2;
	while (curr_a != -1 && curr_b != -1) {
		if (curr_a == curr_b) return curr_a;         // 得到交点
		curr_a = node[curr_a].next;
		curr_b = node[curr_b].next;
		if (curr_a == -1 && curr_b == -1) return -1; // 没找到，返回-1
		if (curr_a == -1) curr_a = s2;               // 接入b链
		if (curr_b == -1) curr_b = s1;               // 接入a链
	}
	return -1;
}

int main() {
	parse_input();
	int ans = get_intersection(s1, s2);
	if (ans == -1) { printf("-1"); return 0; }
	printf("%05d", ans);
}

1052 Linked List Sorting (25分)

image-20200406210154317

解法一：二路归并（递归法）

标准的链表归并排序

#include<iostream>

struct Node {
	int address = -1;
	int val = -1;
	int next = -1;
} node[100002];

int address, val, next, num, head;

void parse_input() {
	scanf("%d%d", &num, &head);
	for (int i = 0; i < num; i++) {
		scanf("%d%d%d", &address, &val, &next);
		node[address] = { address,val,next };
	}
}

int get_len(int head) {
	int len = 0;
	for (int i = head; i != -1; i = node[i].next) len++;
	return len;
}

int merge_sort(int head) {
	if (head == -1 || node[head].next == -1) return head; // 递归结束条件
	int fast = node[head].next, slow = head;
	while (fast != -1 && node[fast].next != -1) {         // 定位到链表中点
		slow = node[slow].next;
		fast = node[node[fast].next].next;
	}
	int tmp = node[slow].next;
	node[slow].next = -1;                                 // 截断前半段
	int left = merge_sort(head);                          // 递归左半边
	int right = merge_sort(tmp);                          // 递归右半边
	int h = 100001;
	while (left != -1 && right != -1) {                   // 转化为了 Merge two sorted list
		if (node[left].val < node[right].val) {
			node[h].next = left;
			left = node[left].next;
		}
		else {
			node[h].next = right;
			right = node[right].next;
		}
		h = node[h].next;
	}
	node[h].next = left != -1 ? left : right;
	return node[100001].next;
}

int main() {
	parse_input();
	head = merge_sort(head);
	int len = get_len(head);
	if (len == 0) { printf("0 -1"); return 0; }
	printf("%d %05d\n", len, head);
	for (int i = head; i != -1; i = node[i].next) {
		printf("%05d %d ", node[i].address, node[i].val);
		if (node[i].next != -1) printf("%05d\n", node[i].next);
		else printf("-1\n");
	}
}

**迭代法归并

int merge_sort(int head) {
    int len = get_len(head);
    
    
}

解法二：快排

int quick_sort(int head) {
    
}

1097 Deduplication on a Linked List (25分)

image-20200407165043580

解法一：模拟HashSet

同理也可以用unordered_set，比这个多写几行但是节省空间

#include<iostream>

struct Node {
	int val = -1;
	int next = -1;
} node[100003];

int address, val, next, num, head;
bool set[10000] = { false };

void parse_input() {
	scanf("%d%d", &head, &num);
	for (int i = 0; i < num; i++) {
		scanf("%d%d%d", &address, &val, &next);
		node[address] = { val,next };
	}
}

void get_list(int m_head, int r_head) {
	if (head == -1) return;
	int h = m_head, r = r_head;
	for (int i = head; i != -1; i = node[i].next) {
		if (!set[abs(node[i].val)]) {
			set[abs(node[i].val)] = true;
			node[h].next = i;
			h = i;
		}
		else {
			node[r].next = i;
			r = i;
		}
	}
	node[h].next = node[r].next = -1;
}

int main() {
	parse_input();
	int m_head = 100001, r_head = 100002;
	get_list(m_head, r_head);
	for (int i = node[m_head].next; i != -1; i = node[i].next) {
		printf("%05d %d ", i, node[i].val);
		if (node[i].next != -1)printf("%05d\n", node[i].next);
		else printf("-1\n");
	}

	for (int i = node[r_head].next; i != -1; i = node[i].next) {
		printf("%05d %d ", i, node[i].val);
		if (node[i].next != -1)printf("%05d\n", node[i].next);
		else printf("-1\n");
	}

}

1133 Splitting A Linked List (25分)

image-20200407180332306

完整解法

和上题思路完全一样，注意一下拼接三条子链的时候，如果二链为-1，要将一链接在三链上，否则将会丢失三链的数据

#include<iostream>

struct Node {
	int val = -1;
	int next = -1;
} node[100004];

int address, val, next, K, num, head;
bool set[10000] = { false };

void parse_input() {
	scanf("%d%d%d", &head, &num, &K);
	for (int i = 0; i < num; i++) {
		scanf("%d%d%d", &address, &val, &next);
		node[address] = { val,next };
	}
}

void gen_list(int n_head, int k_head, int p_head) {
	int n = n_head, k = k_head, p = p_head;
	for (int i = head; i != -1; i = node[i].next) {
		if (node[i].val < 0) {
			node[n].next = i;
			n = i;
		}
		else if (node[i].val <= K) {
			node[k].next = i;
			k = i;
		}
		else {
			node[p].next = i;
			p = i;
		}
	}
	node[n].next = node[k_head].next == -1 ? node[p_head].next : node[k_head].next;
	node[k].next = node[p_head].next;
	node[p].next = -1;
}

int main() {
	parse_input();
	int n_head = 100001, k_head = 100002, p_head = 100003;
	gen_list(n_head, k_head, p_head);
	for (int i = node[n_head].next; i != -1; i = node[i].next) {
		printf("%05d %d ", i, node[i].val);
		if (node[i].next != -1)printf("%05d\n", node[i].next);
		else printf("-1\n");
	}
}

1074 Reversing Linked List (25分)

image-20200411200937050

解法一：快慢指针==（还没完全AC，不知道被什么卡了）==

#include<iostream>
#include<vector>

int num, head, k, address, val, next;
struct Node {
	int val;
	int next = -1;
} node[100000];

void parseInput() {
	std::ios::sync_with_stdio(false); std::cin.tie(0); // 取消同步以加快iostream
	std::cin >> head >> num >> k;
	for (int i = 0; i < num; i++) {
		std::cin >> address >> val >> next;
		node[address] = { val,next };
	}
}

int reverseLinkedList(int k) {
	int prev, curr = head, tail = head, i = 0;
	for (int i = 1; i < k ; i++) tail = node[tail].next; // 定位到第k位
	prev = node[tail].next;                              // 准备将k以后作为前k尾部的next
	node[tail].next = -1;                                // 截断前k位，方便反转
	while (curr != -1) {                                 // 反转链表 
		int next = node[curr].next;
		node[curr].next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}

int main() {
	parseInput();
	head = reverseLinkedList(k);
	for (int i = head; i != -1; i = node[i].next) {
		printf("%05d %d ", i, node[i].val);
		if (node[i].next != -1) printf("%05d\n", node[i].next);
		else printf("-1\n");
	}
}
© 2020 Overyam - Powered by Hexo - Theme Chan