鏈表左右反轉(zhuǎn)：1->2->3->4修改為1->4->2->3， 1->2->3->4->5->6 修改為 1->6->2->5->3->4 c++怎么寫？
方法：
1. 后半段反轉(zhuǎn)，然后前半段和后半段交叉合并
2. 反轉(zhuǎn)的代碼，可以不用dfs寫，可以用cur、next、pre的方式寫
注意：
1. n的數(shù)目：是否算開頭，還有奇偶處理
2. 切斷前半段：mid_前一個→next = NULL
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 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 }
遇到的問題：
用形參d=NULL，沒有改變鏈表情況
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 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 }
你的代碼中，調(diào)用work(d1)后d1沒有被修改，核心原因是C++ 函數(shù)參數(shù)傳遞采用 “值傳遞” 方式，函數(shù)內(nèi)部修改的是指針的副本，而非外部原始指針。
具體分析：
在work(node *d)函數(shù)中：
- 當(dāng)你調(diào)用
work(d1)時，編譯器會創(chuàng)建d1的一個副本（即d是d1的拷貝，兩者指向同一個節(jié)點，但本身是不同的指針變量）。 - 函數(shù)內(nèi)執(zhí)行
d = NULL，只是將這個副本指針d設(shè)為NULL，而外部的原始指針d1仍然指向原來的節(jié)點（值為 1 的節(jié)點）。
這就像：你給朋友復(fù)制了一把家門鑰匙（d），朋友把自己的鑰匙扔了（d = NULL），但你手里的原鑰匙（d1）依然能開門。
驗證：
可以在函數(shù)內(nèi)打印指針地址，清晰看到兩者的區(qū)別：
cpp
運行
`void work(node * d) { cout << "函數(shù)內(nèi)修改前d的地址：" << &d << endl; d = NULL; cout << "函數(shù)內(nèi)修改后d的地址：" << &d << "，值：" << d << endl; }
int main() { // ...（初始化鏈表代碼） cout << "main中d1的地址：" << &d1 << "，值：" << d1 << endl; work(d1); cout << "調(diào)用work后d1的值：" << d1 << endl; // 依然指向原節(jié)點 // ... }`
輸出會顯示：d和d1是不同的指針變量（地址不同），d的修改不影響d1。
如何真正修改外部指針？
若要在函數(shù)內(nèi)修改外部指針d1，需要傳遞指針的引用（node*&）：
cpp
運行
// 改為引用傳遞 void work(node *&d) { // 注意這里的&，表示d是d1的引用（別名） d = NULL; // 此時修改的是外部d1本身 }
修改后，調(diào)用work(d1)會將d1設(shè)為NULL，print(d1)將不會輸出任何內(nèi)容。
總結(jié)：
- C++ 中指針作為函數(shù)參數(shù)時，默認是 “值傳遞”，函數(shù)內(nèi)修改的是副本，不影響外部指針。
- 若要通過函數(shù)修改外部指針，需使用指針的引用（
node*&） 或二級指針（node**）。
你的代碼中由于使用了值傳遞，work(d1)并未改變d1的指向，因此print(d1)仍會輸出原鏈表1->2->3->4。
浙公網(wǎng)安備 33010602011771號