社区 › 安全 › 链表左右反转：1->2->3->4修改为1->4->2->3

二艰糖 发表于 2025-11-5 13:15:05

链表左右反转：1->2->3->4修改为1->4->2->3

 
方法：
1. 后半段反转，然后前半段和后半段交叉合并
2. 反转的代码，可以不用dfs写，可以用cur、next、pre的方式写
 
注意：
1. n的数目：是否算开头，还有奇偶处理
2. 切断前半段：mid_前一个→next = NULL

 
1 #include2 #include3 #include4 #include5 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 }
 
遇到的问题：
用形参d=NULL，没有改变链表情况
1 #include2 #include3 #include4 #include5 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 }
 
你的代码中，调用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。
如何真正修改外部指针？

若要在函数内修改外部指针d1，需要传递指针的引用（node*&）：
cpp
运行
// 改为引用传递 void work(node *&d) { // 注意这里的&，表示d是d1的引用（别名） d = NULL; // 此时修改的是外部d1本身 }
修改后，调用work(d1)会将d1设为NULL，print(d1)将不会输出任何内容。
总结：


[*]C++ 中指针作为函数参数时，默认是 “值传递”，函数内修改的是副本，不影响外部指针。
[*]若要通过函数修改外部指针，需使用指针的引用（node*&） 或二级指针（node**）。
你的代码中由于使用了值传递，work(d1)并未改变d1的指向，因此print(d1)仍会输出原链表1->2->3->4。

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

昆拗干 发表于 2025-11-9 00:32:15

很好很强大我过来先占个楼 待编辑

癖艺泣 发表于 2025-11-30 06:55:57

感谢发布原创作品，程序园因你更精彩

巫雪艷 发表于 2025-12-4 10:25:33

东西不错很实用谢谢分享

挚魉 发表于 2025-12-15 08:50:12

前排留名，哈哈哈

育局糊 发表于 2025-12-27 14:17:53

感谢分享，下载保存了，貌似很强大

肿圬后 发表于 2026-1-3 01:58:28

鼓励转贴优秀软件安全工具和文档！

闹忧踫 发表于 2026-1-3 21:56:50

很好很强大我过来先占个楼 待编辑

磁呃泵 发表于 2026-1-11 17:41:13

不错，里面软件多更新就更好了

氛疵 发表于 2026-1-13 18:31:26

懂技术并乐意极积无私分享的人越来越少。珍惜

凌彦慧 发表于 2026-1-15 08:41:22

感谢分享，下载保存了，貌似很强大

百里宵月 发表于 2026-1-16 18:35:09

用心讨论，共获提升！

玻倌瞽 发表于 2026-1-18 12:29:06

感谢发布原创作品，程序园因你更精彩

廖彗云 发表于 2026-1-18 13:51:40

谢谢分享，辛苦了

阴昭昭 发表于 2026-1-21 06:48:57

热心回复！

骆贵 发表于 2026-1-21 17:57:05

yyds。多谢分享

诸婉丽 发表于 2026-1-24 03:07:24

感谢发布原创作品，程序园因你更精彩

靛尊 发表于 2026-1-25 09:59:28

谢谢分享，试用一下

歇凛尾 发表于 2026-1-26 02:46:04

感谢，下载保存了

鞭氅 发表于 2026-1-26 11:36:33

懂技术并乐意极积无私分享的人越来越少。珍惜

查看完整版本: 链表左右反转：1->2->3->4修改为1->4->2->3