题目描述

已知循环双链表的节点定义如下：

struct Node {
	int val;
	Node *nxt, *pre;
}; 
Node *head; // 头节点
int tot; // 统计节点数量

你的任务是实现 insertNode 函数：

• 传入两个节点 p 和 q。
• 在节点 p 后面插入节点 q。

测试程序

#include <bits/stdc++.h>
using namespace std;
struct Node {
	int val;
	Node *nxt, *pre;
}; 
Node *head;
int tot;
// 请在此处实现 insertNode 函数  
// ... 
int main() {
	// 初始化头节点 
	head = new Node;
	head->nxt = head;
	head->pre = head;
	int v1, v2, v3;
	cin >> v1 >> v2 >> v3;
	Node *n1 = new Node;
	n1->val = v1;
	Node *n2 = new Node;
	n2->val = v2;
	Node *n3 = new Node;
	n3->val = v3;
	insertNode(head, n1);	// 在头节点后插入节点 n1 
	insertNode(n1, n2);		// 在节点 n1 后插入节点 n2 
	insertNode(n1, n3);		// 在节点 n1 后插入节点 n3
	// 正序遍历链表 
	Node *t = head->nxt;
	for (int i = 1; i <= 3; i++) {
		cout << t->val << " ";
		t = t->nxt; 
	}
	cout << endl;
	// 倒序遍历链表 
	t = head->pre;
	for (int i = 1; i <= 3; i++) {
		cout << t->val << " ";
		t = t->pre; 
	}
	delete head; delete n1; delete n2; delete n3;
	return 0;
}

题型说明

解题时可以把题目提供的程序复制到编译器中，编写对应所需的函数，测试通过后只需要提交所需的函数，如果提交完整程序反而会 WA。

格式要求

输入格式

输入 $3$ 个 int 类型的整数，代表链表 $3$ 个节点的数据域。

输出格式

输出 $2$ 行，每行 $3$ 个空格隔开的数字，分别代表正序遍历和倒序遍历链表的结果。

样例

1 2 3

1 3 2
2 3 1