1105 链表合并 (25 分)

题目

题目链接

题解

链表。

有点像双指针的感觉。

整体思路： 假设 L1 的长度始终大于 L2 的长度，那么 L1 正序输出2个节点，L2 倒序输出1个节点，直到L2到头。如果 L1 还剩节点未输出，则顺序输出完。

处理：

1. 比较一下L1和L2长度，如果L2长度长，则交换一下L1，L2；
2. L2要倒序输出，所以需要设置pre，保存每个节点的前面一个节点。

我觉得指针最难的还是判断结束（while的结束条件）

代码

#include
using namespace std;

struct Node {
	int ne, val, pre;
} node[110000];

int main()
{
	int L1, L2, n;
	cin >> L1 >> L2 >> n;
	for (int i = 0;i > ad >> val >> ne;
		node[ad].val = val;
		node[ad].ne = ne;
		node[ne].pre = ad;
	} 
	int p = L1, q = L2;
	while (~p && ~q) p = node[p].ne, q = node[q].ne;
	if (p == -1) swap (L1, L2); // 保证 L1 长度大于 L2 长度 
	node[L2].pre = -1;
	
	while (~node[L2].ne) L2 = node[L2].ne; // 让 L2 先到原串的末尾，向前输出就实现了逆序 
	while (~L2) {
		// 输出两个 L1 串节点 ，且肯定不是合并后串的结尾 
		printf ("%05d %d %05d\n", L1, node[L1].val, node[L1].ne); 
		L1 = node[L1].ne;
		printf ("%05d %d %05d\n", L1, node[L1].val, L2); // 因为这之后要输出 L2 的元素，所以输出的next节点的地址应该是L2，而不是node[L1].ne 
		L1 = node[L1].ne;
		
		if (node[L2].pre == -1 && L1 == -1) printf ("%05d %d -1\n", L2, node[L2].val); // 只有 L1 没了（以L2的最后一个元素作为合并后串的结尾）才输出-1 
		else printf ("%05d %d %05d\n", L2, node[L2].val, L1); // next 为 L1 
		L2 = node[L2].pre;
	}
	
	while (~L1) { // L1 多出的部分，顺序输出 
		if (node[L1].ne == -1) printf ("%05d %d -1\n", L1, node[L1].val);
		else printf ("%05d %d %05d\n", L1, node[L1].val, node[L1].ne);
		L1 = node[L1].ne;
	}
	
	return 0;
}