1->2->3->4->5->6 修改为 1->6->2->5->3->4 c++怎么写？

撒阗奕 2025-10-2 12:54

方法：

1. 后半段反转，然后前半段和后半段交叉合并

2. 反转的代码，可以不用dfs写，可以用cur、next、pre的方式写

注意：

1. n的数目：是否算开头，还有奇偶处理

2. 切断前半段：mid_前一个→next = NULL

[code] 1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define ll long long 8 9 const int maxn=1e5+10; 10 11 struct node { 12 int val; 13 node *next; 14 }; 15 16 /* 17 void work(node * d) { 18 d = NULL; 19 } 20 */ 21 22 void work(node * d) { 23 node * temp, * mid, * cur, * nex, * pre, * last, * first, * first_2, * last_2; 24 int n = 0, n_half; 25 temp = d; 26 while (temp) { 27 temp = temp -> next; 28 n++; 29 } 30 31 n_half = (n + 1) / 2 - 1; 32 mid = d; 33 while (n_half --) { 34 mid = mid -> next; 35 } 36 temp = mid; 37 mid = mid -> next; 38 temp->next = nullptr; 39 40 cur = mid; 41 pre = nullptr; 42 while (cur) { 43 nex = cur -> next; 44 cur -> next = pre; 45 46 pre = cur; 47 cur = nex; 48 } 49 50 last = pre; 51 first = d; 52 while (first && last) { 53 first_2 = first -> next; 54 last_2 = last -> next; 55 56 first -> next = last; 57 last -> next = first_2; 58 59 first = first_2; 60 last = last_2; 61 } 62 //if (first != NULL) //odd 63 // first -> next = NULL; 64 } 65 66 void print(node * d) { 67 while (d) { 68 printf("%d ", d -> val); 69 d = d -> next; 70 } 71 } 72 73 void init_1(node * d1) { 74 node * d2 = new node(); 75 node * d3 = new node(); 76 node * d4 = new node(); 77 78 d1 -> val = 1; 79 d1 -> next = d2; 80 d2 -> val = 2; 81 d2 -> next = d3; 82 d3 -> val = 3; 83 d3 -> next = d4; 84 d4 -> val = 4; 85 d4 -> next = nullptr; 86 } 87 88 void init_2(node * d1) { 89 node * d2 = new node(); 90 node * d3 = new node(); 91 node * d4 = new node(); 92 node * d5 = new node(); 93 node * d6 = new node(); 94 95 d1 -> val = 1; 96 d1 -> next = d2; 97 d2 -> val = 2; 98 d2 -> next = d3; 99 d3 -> val = 3; 100 d3 -> next = d4; 101 d4 -> val = 4; 102 d4 -> next = d5; 103 d5 -> val = 5; 104 d5 -> next = d6; 105 d6 -> val = 6; 106 d6 -> next = nullptr; 107 } 108 109 void init_3(node * d1) { 110 node * d2 = new node(); 111 node * d3 = new node(); 112 node * d4 = new node(); 113 node * d5 = new node(); 114 115 d1 -> val = 1; 116 d1 -> next = d2; 117 d2 -> val = 2; 118 d2 -> next = d3; 119 d3 -> val = 3; 120 d3 -> next = d4; 121 d4 -> val = 4; 122 d4 -> next = d5; 123 d5 -> val = 5; 124 d5 -> next = nullptr; 125 } 126 127 void init_4(node * d1) { 128 node * d2 = new node(); 129 d1 -> val = 1; 130 d1 -> next = d2; 131 d2 -> val = 2; 132 d2 -> next = nullptr; 133 } 134 135 void init_5(node * d1) { 136 d1 -> val = 1; 137 d1 -> next = nullptr; 138 } 139 140 int main() 141 { 142 node * d1 = new node(); 143 //init_1(d1); 144 //init_2(d1); 145 init_3(d1); 146 //init_4(d1); 147 //init_5(d1); 148 149 work(d1); 150 151 print(d1); 152 153 return 0; 154 }[/code]

遇到的问题：

用形参d=NULL，没有改变链表情况

你的代码中，调用work(d1)后d1没有被修改，核心原因是C++ 函数参数传递采用 “值传递” 方式，函数内部修改的是指针的副本，而非外部原始指针。

具体分析：

在work(node *d)函数中：

当你调用work(d1)时，编译器会创建d1的一个副本（即d是d1的拷贝，两者指向同一个节点，但本身是不同的指针变量）。
函数内执行d = NULL，只是将这个副本指针d设为NULL，而外部的原始指针d1仍然指向原来的节点（值为 1 的节点）。

这就像：你给朋友复制了一把家门钥匙（d），朋友把自己的钥匙扔了（d = NULL），但你手里的原钥匙（d1）依然能开门。

验证：

可以在函数内打印指针地址，清晰看到两者的区别：

cpp

运行

`void work(node * d) { cout << "函数内修改前d的地址：" << &d << endl; d = NULL; cout << "函数内修改后d的地址：" << &d << "，值：" << d << endl; }

int main() { // ...（初始化链表代码） cout << "main中d1的地址：" << &d1 << "，值：" << d1 << endl; work(d1); cout << "调用work后d1的值：" << d1 << endl; // 依然指向原节点 // ... }`

输出会显示：d和d1是不同的指针变量（地址不同），d的修改不影响d1。