首页 计算机科学 数据结构与算法 C++

敬爱的李老师在期末才把线性表的题放出来，我说我怎么链表这么糊里糊涂就结束了。🍢🧆🥘🍲🍦🥧🍝

刚好我先去把线性表那一块的笔记复习一下。

# 1. 合并两个有序链表

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
1: 合并两个有序链表
描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入
输入两个顺序表l1，l2，l1和l2均按非递减顺序排列，两个链表的节点数目范围是 [0, 50]，-100 <= Node.val <= 100
-1表示链表结束符
输出
输出合并后的顺序表
输入样例
1 2 4 -1
1 3 4 -1
输出样例
1 1 2 3 4 4
*/
//简单的双链表合成单链表，两个指针
//解法1，正经的链表
//解法2，数组仿写链表
#include <iostream>
using namespace std;

struct Node {
	Node *next;
	int data;
};

Node* InputList() {
	int input;
	Node *root = new Node;
	Node *node = root;
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}

Node* SortA_B(Node *A,Node*B) {
	Node *root = new Node;
	Node* node = root;
	A = A->next;
	B = B->next;
    while (A || B) {//A和B都还有
        if (A && (!B || A->data <= B->data)) { // A还有，（B为空或者A的值小于等于B） 加入A
            Node* next = new Node;
            next->data = A->data;
            node->next = next;
            next->next = nullptr;
            node = next; // 更新node指针
            A = A->next;
        }
        else{ //B还有，（A为空或者B的值小于等于A） 加入A
            Node* next = new Node;
            next->data = B->data;
            node->next = next;
            next->next = nullptr;
            node = next; // 更新node指针
            B = B->next;
        }//注意：等于只会执行一次，妙
    }
    return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
    cout << endl;
}

int main() {
	Node* A = InputList();
	Node* B = InputList();
	Node* C = SortA_B(A, B);
	print(C);
	return 0;
}

# 2. 删除排序链表中的重复元素

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
2: 删除排序链表中的重复元素
描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表
输入
输入已排序的链表，链表中节点数目在范围 [0, 300] 内，-100 <= Node.val <= 100，题目数据保证链表已经按升序排列
-1表示链表结束符
输出
输出已排序的链表
输入样例

1 1 2 3 3 -1
输出样例

1 2 3
*/
//搬第一题的东西，比较简单
#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};

Node* InputList() {
	int input;
	Node* root = new Node;
	Node* node = root;
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
void init(Node* root) {
	root->data = -10000;
	root->next = nullptr;
}
Node* DeleteRe(Node* Head) {
	Node* root = new Node;
	init(root);
	Node* node = root;
	Head = Head->next;
	while (Head) {
		if (Head->data != node->data) {
			Node* next = new Node;
			next->data =Head->data;
			node->next = next;
			next->next = nullptr;
			node = next;
		}
		Head = Head->next;
	}
	return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

int main() {
	Node* input = InputList();
	Node* Result = DeleteRe(input);
	print(Result);
	return 0;
}

# 3. 移除链表元素

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
3: 移除链表元素
描述
给你一个链表的头节点 head 和一个整数val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点
输入
输入链表和val，列表中的节点数目在范围 [0, 10^4] 内，1 <= Node.val <= 50，0 <= val <= 50
-1表示链表结束符
输出
输出移除元素的链表
输入样例

1 2 6 3 4 5 6 -1 6
输出样例

1 2 3 4 5
*/
//搬第一题的东西，比较简单
#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}

Node* Delete(Node* Head,int temp) {
	Node* root = Head;
	while (Head) {
		//警惕1 2 2 -1 2这组测试数据
		if (Head->next && Head->next->data == temp) {//下一个出现问题存在
			//用一个op来临时删除，直到没有删完为止，考虑它最后一个的问题，小小调整
			Node* op = Head->next;
			while (op && op->data == temp) {
				if (op->next) {
					op = op->next;
				}
				else op = nullptr;	
			}
			Head->next = op;//更新head的next
		}
		else Head=Head->next;
	}
	return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

int main() {
	Node* input = InputList();
	int num;
	cin >> num;
	Node* Result = Delete(input,num);
	print(Result);
	return 0;
}

# 4. 从尾到头打印链表（小疑问，前插法）

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
4: 从尾到头打印链表
描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
输入
输入链表，0 <= 链表长度 <= 10000
-1表示链表结束符
输出
输出反转后的链表
输入样例

1 2 6 3 4 5 6 -1
输出样例

6 5 4 3 6 2 1
*/
//搬第一题的东西，比较简单
#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
//留个疑问
Node* ChangeTowards1111(Node* input) {
	Node* root = new Node; // 旋转后的根
	init(root);
	// 前插
	input = input->next; // 跳到首元节点
	while (input) {//图示：1<-2插入3，3先指向1，2再指向3，结束
		Node* op = input;
		op->next = root->next; // 前插操作
		root->next = op; // 更新root->next指针

		input = input->next; // input向下走
	}
	return root;
}//这个函数为啥错了

Node* ChangeTowards(Node* input) {
	Node* root = new Node; // 旋转后的头节点
	init(root);
	// 前插
	input = input->next; // 跳到首元节点
	while (input) {
		Node* op = input;
		input = input->next; // 更新input指针

		op->next = root->next; // 前插操作
		root->next = op; // 更新root->next指针
	}
	return root;
}

void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

int main() {
	Node* input = InputList();
	Node* Result = ChangeTowards(input);
	print(Result);
	return 0;
}

# 5. 合并两个链表

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
5: 合并两个链表
描述
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
输入
3 <= list1.length <= 10^4
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10^4
-1作为链表结束符
输出
输出链表
输入样例

0 1 2 3 4 5 -1
3
4
1000000 1000001 1000002 -1
输出样例

0 1 2 1000000 1000001 1000002 5
*/

#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -1000000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
Node* DeleteA_AndB(Node* A, Node* B, int a, int b) {
	Node* root = A;
	int ans = 0;

	Node* Astart = new Node;//a处
	Astart = B->next;//Astart接上B的首元
	Node* Aend = new Node;//b处
	while (ans != b+2) {//注意是b+2
		ans++;
		A = A->next;
	}
	Aend = A;//等于此时的A
	//cout << Aend->data<<endl;
	while (B->next) {//到最后一个地方
		B = B->next;
	}
	B->next = Aend;//接上Aend,b处
	//此时Astart后面的链子就是我们想要的的了，我们接到A中即可
	Node* Result = root;
	for (int ans = 0; ans < a; ans++) {
		root = root->next;
	}//到A处
	root->next = Astart;

	return Result;
}

void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

int main() {
	Node* A = InputList();
	int a, b;
	cin >> a >> b;
	Node* B = InputList();
	Node* Result = DeleteA_AndB(A,B,a,b);
	print(Result);
	return 0;
}

# 6. 二进制链表转整数 (同 4 题)

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
6.二进制链表转整数
描述
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值
输入
输入链表，链表不为空。链表的结点总数不超过 30。每个结点的值不是 0 就是 1。
-1表示链表结束符
输出
输出十进制数
输入样例

1 0 1 -1
输出样例

5
*/

//简单的想法，基于第四题，倒过来之后，直接相加即可。
#include <iostream>
#include <math.h>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}

Node* ChangeTowards(Node* input) {
	Node* root = new Node; // 旋转后的头节点
	init(root);
	// 前插
	input = input->next; // 跳到首元节点
	while (input) {
		Node* op = input;
		input = input->next; // 更新input指针

		op->next = root->next; // 前插操作
		root->next = op; // 更新root->next指针
	}
	return root;
}

void Coal(Node* result) {
	result = result->next;
	int q = 0;//指数
	int num = 0;
	while (result) {
		int p = pow(2, q);
		num += result->data * p;
		q++;
		result = result->next;
	}
	cout << num<<endl;
}

int main() {
	Node* input = InputList();
	Node* Result = ChangeTowards(input);
	Coal(Result);
	return 0;
}

# 7. 两数相加 Ⅱ

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
7: 两数相加Ⅱ
描述
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
输入
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0
-1表示链表结束符
输出
输出链表
输入样例

7 2 4 3 -1
5 6 4 -1
输出样例

7 8 0 7
*/

//简单的想法，基于第四题，倒过来之后，直接相加即可。
//相加完之后，再倒一次
#include <iostream>
#include <math.h>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
//转向函数
Node* ChangeTowards(Node* input) {
	Node* root = new Node; // 旋转后的头节点
	init(root);
	// 前插
	input = input->next; // 跳到首元节点
	while (input) {
		Node* op = input;
		input = input->next; // 更新input指针

		op->next = root->next; // 前插操作
		root->next = op; // 更新root->next指针
	}
	return root;
}
//十进制计算函数
int Coal(Node *A){
	A = A->next;
	int q = 0;//指数
	int num = 0;
	while (A) {
		int p = pow(10, q);
		num += A->data * p;
		q++;
		A = A->next;
	}
	return num;
}
//加法函数
int And(Node* A, Node* B) {
	int num1 = Coal(A);
	int num2 = Coal(B);
	int result = num1 + num2;
	return result;
}

//十进制转链表（前插法）
Node* NumCreatL(int num) {
	Node* root = new Node;
	init(root);

	int q = 0;//指数
	int tmp = num / 10;
	int node = num - tmp * 10;//获得个位数
	while (num / 10) {
		int tmp = num / 10;
		int data = num - tmp * 10;//获得个位数
		//前插法
		Node* next = new Node;
		next->data = data;
		next->next = root->next;
		root->next = next;
		num /= 10;
	}//最后num变成了一个个位数,原来的最高位
	Node* next = new Node;
	next->data = num;
	next->next = root->next;
	root->next = next;
	
	return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

int main() {
	Node* A = InputList();
	Node* B = InputList();
	Node* Result = NumCreatL(And(ChangeTowards(A), ChangeTowards(B)));
	print(Result);
	return 0;
}

# 8. 反转链表 Ⅱ

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*
反转链表Ⅱ
描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。
输入
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
-1表示链表结束符
输出
输出链表
输入样例

1 2 3 4 5 -1 2 4
输出样例

1 4 3 2 5
*/

//单纯的想法，把它拆分成两个单链表，然后在那个right的哪里，采取前插法

#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

Node* ChangeLefttoRight(Node* L, int left, int right) {
	if (left == right)
		return L;

	Node* tempL = new Node(); // 记录LefttoRight
	init(tempL);
	Node* root = L; // 记录原来的头节点

	int ans = 0;
	Node* prev = nullptr;
	Node* curr = L;

	while (curr) {
		
		
		if (ans >= left) {//前插法
			//解决思想：插入当前节点而不是去插next
//			cout <<ans<<" :"<< curr->data << endl;
			Node* next = curr->next;

			curr->next = tempL->next;
			tempL->next = curr;

			curr = next;
		}
		else {
			curr = curr->next;
		}
		if (ans == right)
			break;
		ans++;
	}

	// 遍历到tempL末尾，接上剩余的L节点
	Node* L1 = tempL->next; // 接起来的索引指针
	//print(tempL);
	while (L1->next) {
		L1 = L1->next;
	}
	L1->next = curr; // 接上剩下的L节点

	// 接上去就好了
	Node* L2 = root; // 接起来的索引指针
	ans = 0;
	while (L2) {
		ans++;
		if (ans == left) {
			L2->next = tempL->next;
			break;
		}
		L2 = L2->next;
	}

	return root;
}
int main() {
	Node* A = InputList();
	int left, right;
	cin >> left >> right;
	Node* Result = ChangeLefttoRight(A, left, right);
	print(Result);
	return 0;
}

# 9. 链表最大孪生和

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*9: 链表最大孪生和
描述
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，
第 i 个节点（下标从 0 开始）的孪生节点为第(n - 1 - i) 个节点 。
比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
输入
输入链表的节点数目是[2, 10 ^ 5] 中的 偶数 。
1 <= Node.val <= 10 ^ 5
- 1是链表结束符
输出
输出孪生和
输入样例

5 4 2 1 - 1
输出样例

6
*/
//
#include <iostream>
#include <queue>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
Node* Copy(Node* L) {
	// 创建一个新链表，并复制原链表的节点
	Node* L2 = new Node;
	init(L2);
	Node* curr = L->next;
	Node* prev = L2;
	while (curr) {
		Node* new_node = new Node;
		new_node->data = curr->data;
		new_node->next = nullptr;
		prev->next = new_node;
		prev = new_node;
		curr = curr->next;
	}
	return L2;
}
//转向函数
Node* ChangeTowards(Node* L) {
	Node* input = L;
	Node* root = new Node; // 旋转后的头节点
	init(root);
	// 前插
	input = input->next; // 跳到首元节点
	while (input) {
		Node* op = input;
		input = input->next; // 更新input指针

		op->next = root->next; // 前插操作
		root->next = op; // 更新root->next指针
	}
	return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}
int Lenth(Node* L) {
	L = L->next;
	int lenth = 0;
	while (L) {
		lenth++;
		L = L->next;
	}
	return lenth;
}
int TwinnedMax(Node* L) {
	Node* L1 = L;
	//print(L1);
	Node* L2 = Copy(L1);//copy
	L2 = ChangeTowards(L2);
	//print(L1);
	//print(L2);
	int lenth = Lenth(L2)/2;

	L1 = L1->next;
	L2 = L2->next;
	
	int ans = 0;
	int result = 0;
	while (ans++<lenth) {
		if (L2->data + L1->data > result) {
			result = L2->data + L1->data;
		}
		L1 = L1->next;
		L2 = L2->next;
	}
	return result;
}



int main() {
	Node* A = InputList();
	int Result = TwinnedMax(A);
	cout << Result << endl;
	return 0;
}

# 10. 和第 7 题重复

行高亮
1

# 11. 重排链表

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*
11: 重排链表
描述
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入
输入链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000
-1表示链表结束符
输出
输出重排链表
输入样例

1 2 3 4 5 -1
输出样例

1 5 2 4 3
*/
//和孪生和一样，换成合起来就行了
#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}
Node* Copy(Node* L) {
	// 创建一个新链表，并复制原链表的节点
	Node* L2 = new Node;
	init(L2);
	Node* curr = L->next;
	Node* prev = L2;
	while (curr) {
		Node* new_node = new Node;
		new_node->data = curr->data;
		new_node->next = nullptr;
		prev->next = new_node;
		prev = new_node;
		curr = curr->next;
	}
	return L2;
}
//转向函数
Node* ChangeTowards(Node* L) {
	Node* input = L;
	Node* root = new Node; // 旋转后的头节点
	init(root);
	// 前插
	input = input->next; // 跳到首元节点
	while (input) {
		Node* op = input;
		input = input->next; // 更新input指针

		op->next = root->next; // 前插操作
		root->next = op; // 更新root->next指针
	}
	return root;
}
void print(Node* result) {
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}
int Lenth(Node* L) {
	L = L->next;
	int lenth = 0;
	while (L) {
		lenth++;
		L = L->next;
	}
	return lenth;
}

Node* ChangeLtoN(Node* L) {//改变链表相邻节点和为n
	Node* L1 = L;
	//print(L1);
	Node* L2 = Copy(L1);//copy
	L2 = ChangeTowards(L2);
	//print(L1);
	//print(L2);
	int lenth = Lenth(L2);

	L1 = L1->next;//到首元节点
	L2 = L2->next;
	
	int ans = 0;
	Node* result = new Node;//根节点
	Node* node = result;//活动指针
	while (ans++ < lenth) {
		if (ans % 2 == 1) {//插L1的值
			Node* next = new Node;//创造节点
			next->data = L1->data;
			node->next = next;
			next->next = nullptr;
			node = next;//更新node为next节点
			L1 = L1->next;
		}
		else {//插L2
			Node* next = new Node;//创造节点
			next->data = L2->data;
			node->next = next;
			next->next = nullptr;
			node = next;//更新node为next节点
			L2 = L2->next;
		}
	}
	return result;
}



int main() {
	Node* A = InputList();
	Node* Result = ChangeLtoN(A);
	print(Result);
	return 0;
}

# 12. 删除倒数第 n 个节点

行高亮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
12: 删除链表的倒数第 N 个结点
描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入
输入链表和要删除的n ，链表中结点的数目为 sz，
1 <= sz <= 30，0 <= Node.val <= 100，1 <= n <= sz
-1表示链表结束符
输出
输出链表
输入样例

1 2 3 4 5 -1
2
输出样例

1 2 3 5
*/
//
#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
void init(Node* root) {//初始化节点
	root->data = -10000;
	root->next = nullptr;
}
Node* InputList() {
	int input;
	Node* root = new Node;//头节点
	init(root);
	Node* node = root;//活动指针
	while (true) {
		cin >> input;
		if (input == -1)
			break;
		Node* next = new Node;//创造节点
		next->data = input;
		node->next = next;
		next->next = nullptr;
		node = next;//更新node为next节点
	}
	return root;
}


void print(Node* result) {
	if (result == nullptr) {
	cout << endl;
	return;
    }
	result = result->next;
	while (result) {
		cout << result->data << " ";
		result = result->next;
	}
	cout << endl;
}

int Lenth(Node* L) {
	L = L->next;
	int lenth = 0;
	while (L) {
		lenth++;
		L = L->next;
	}
	return lenth;
}

Node* Delete(Node* L, int n) {
	Node* root = L;//回去的根

	Node* len = L;
	int lenth = Lenth(len);//求表长
	int num = lenth - n + 1;//删除正向的第num个元素
	L = L->next;
	//cout << "num:" << num << "lenth:" << lenth << endl;
	int ans = 0;
	while (++ans) {
		//cout << "ans:" <<ans<< endl;
		if (ans == num && num != lenth) {//删除非最后一个//停在当前，复制当前为下一个的状态
			//cout << "删除成功"<< "ans:" << ans << endl;
			L->data = L->next->data;
			L->next = L->next->next;
			break;
		}
		else if (ans == num - 1 && num == lenth) {//删除最后一个//停在倒数第2个
			//cout << "删除成功" << "ans:" << ans+1 << endl;
			L->next = nullptr;
			break;
		}
		else if (ans == num && num == 1 && lenth == 1) {//删第一个且只有一个
			return nullptr;
		}
		else {
			//cout << "未删除" << endl;
			L = L->next;
		}
	}
   
	return root;
}


int main() {
	Node* A = InputList();
	int n;
	cin >> n;
	Node* Result = Delete(A,n);
	print(Result);
	return 0;
}