單鏈表的操作算法是筆試面試中較為常見的題目。本文將著重介紹平時(shí)面試中常見的關(guān)于鏈表的應(yīng)用題目。
本文大概 一萬五千字 ，建議閱讀時(shí)間為一個(gè)小時(shí)，請先收藏再閱讀，平時(shí)也可以拿出來多看幾遍。
題目：輸入一個(gè)單鏈表，輸出此鏈表中的倒數(shù)第 K 個(gè)節(jié)點(diǎn)。（去除頭結(jié)點(diǎn)，節(jié)點(diǎn)計(jì)數(shù)從 1 開始）。
（1）遍歷單鏈表，遍歷同時(shí)得出鏈表長度 N 。
（2）再次從頭遍歷，訪問至第 N - K 個(gè)節(jié)點(diǎn)為所求節(jié)點(diǎn)。
/*計(jì)算鏈表長度*/
int listLength(ListNode* pHead){
int count = 0;
ListNode* pCur = pHead->next;
if(pCur == NULL){
printf('error');
}
while(pCur){
count++;
pCur = pCur->pNext;
}
return count;
}
/*查找第k個(gè)節(jié)點(diǎn)的值*/
ListNode* searchNodeK(ListNode* pHead, int k){
int i = 0;
ListNode* pCur = pHead;
//計(jì)算鏈表長度
int len = listLength(pHead);
if(k > len){
printf('error');
}
//循環(huán)len-k+1次
for(i=0; i <>1; i++){
pCur = pCur->next;
}
return pCur;//返回倒數(shù)第K個(gè)節(jié)點(diǎn)
}
采用這種遍歷方式需要兩次遍歷鏈表，時(shí)間復(fù)雜度為O(n※2)?？梢娺@種方式最為簡單,也較好理解，但是效率低下。
（1）定義num = k
（2）使用遞歸方式遍歷至鏈表末尾。
（3）由末尾開始返回，每返回一次 num 減 1
（4）當(dāng) num 為 0 時(shí)，即可找到目標(biāo)節(jié)點(diǎn)
int num;//定義num值
ListNode* findKthTail(ListNode* pHead, int k) {
num = k;
if(pHead == NULL)
return NULL;
//遞歸調(diào)用
ListNode* pCur = findKthTail(pHead->next, k);
if(pCur != NULL)
return pCur;
else{
num--;// 遞歸返回一次，num值減1
if(num == 0)
return pHead;//返回倒數(shù)第K個(gè)節(jié)點(diǎn)
return NULL;
}
}
使用遞歸的方式實(shí)現(xiàn)仍然需要兩次遍歷鏈表，時(shí)間復(fù)雜度為O(n※2)。
（1）定義兩個(gè)指針 p1 和 p2 分別指向鏈表頭節(jié)點(diǎn)。
（2）p1 前進(jìn) K 個(gè)節(jié)點(diǎn)，則 p1 與 p2 相距 K 個(gè)節(jié)點(diǎn)。
（3）p1，p2 同時(shí)前進(jìn)，每次前進(jìn) 1 個(gè)節(jié)點(diǎn)。
（4）當(dāng) p1 指向到達(dá)鏈表末尾，由于 p1 與 p2 相距 K 個(gè)節(jié)點(diǎn)，則 p2 指向目標(biāo)節(jié)點(diǎn)。
ListNode* findKthTail(ListNode *pHead, int K){
if (NULL == pHead || K == 0)
return NULL;
//p1，p2均指向頭節(jié)點(diǎn)
ListNode *p1 = pHead;
ListNode *p2 = pHead;
//p1先出發(fā)，前進(jìn)K個(gè)節(jié)點(diǎn)
for (int i = 0; i <>
if (p1)//防止k大于鏈表節(jié)點(diǎn)的個(gè)數(shù)
p1 = p1->_next;
else
return NULL;
}
while (p1)//如果p1沒有到達(dá)鏈表結(jié)尾，則p1，p2繼續(xù)遍歷
{
p1 = p1->_next;
p2 = p2->_next;
}
return p2;//當(dāng)p1到達(dá)末尾時(shí)，p2正好指向倒數(shù)第K個(gè)節(jié)點(diǎn)
}
可以看出使用雙指針法只需遍歷鏈表一次，這種方法更為高效時(shí)間復(fù)雜度為O(n)，通常筆試題目中要考的也是這種方法。
單鏈表中的環(huán)是指鏈表末尾的節(jié)點(diǎn)的 next 指針不為 NULL ，而是指向了鏈表中的某個(gè)節(jié)點(diǎn)，導(dǎo)致鏈表中出現(xiàn)了環(huán)形結(jié)構(gòu)。
鏈表中有環(huán)示意圖：
鏈表的末尾節(jié)點(diǎn) 8 指向了鏈表中的節(jié)點(diǎn) 3，導(dǎo)致鏈表中出現(xiàn)了環(huán)形結(jié)構(gòu)。
對(duì)于鏈表是否是由有環(huán)的判斷方法有哪些呢？
（1）遍歷鏈表，記錄已訪問的節(jié)點(diǎn)。
（2）將當(dāng)前節(jié)點(diǎn)與之前以及訪問過的節(jié)點(diǎn)比較，若有相同節(jié)點(diǎn)則有環(huán)。
否則，不存在環(huán)。
這種窮舉比較思想簡單，但是效率過于低下，尤其是當(dāng)鏈表節(jié)點(diǎn)數(shù)目較多，在進(jìn)行比較時(shí)花費(fèi)大量時(shí)間，時(shí)間復(fù)雜度大致在 O(n^2)。這種方法自然不是出題人的理想答案。如果筆試面試中使用這種方法，估計(jì)就要跪了，忘了這種方法吧。
既然在窮舉遍歷時(shí)，元素比較過程花費(fèi)大量時(shí)間，那么有什么辦法可以提高比較速度呢？
（1）首先創(chuàng)建一個(gè)以節(jié)點(diǎn) ID 為鍵的 HashSe t集合，用來存儲(chǔ)曾經(jīng)遍歷過的節(jié)點(diǎn)。
（2）從頭節(jié)點(diǎn)開始，依次遍歷單鏈表的每一個(gè)節(jié)點(diǎn)。
（3）每遍歷到一個(gè)新節(jié)點(diǎn)，就用新節(jié)點(diǎn)和 HashSet 集合當(dāng)中存儲(chǔ)的節(jié)點(diǎn)作比較，如果發(fā)現(xiàn) HashSet 當(dāng)中存在相同節(jié)點(diǎn) ID，則說明鏈表有環(huán)，如果 HashSet 當(dāng)中不存在相同的節(jié)點(diǎn) ID，就把這個(gè)新節(jié)點(diǎn) ID 存入 HashSet ，之后進(jìn)入下一節(jié)點(diǎn)，繼續(xù)重復(fù)剛才的操作。
假設(shè)從鏈表頭節(jié)點(diǎn)到入環(huán)點(diǎn)的距離是 a ，鏈表的環(huán)長是 r 。而每一次 HashSet 查找元素的時(shí)間復(fù)雜度是 O(1), 所以總體的時(shí)間復(fù)雜度是 1 * ( a + r ) = a + r，可以簡單理解為 O(n) 。而算法的空間復(fù)雜度還是 a + r - 1，可以簡單地理解成 O(n) 。
（1）定義兩個(gè)指針分別為 slow，fast，并且將指針均指向鏈表頭節(jié)點(diǎn)。
（2）規(guī)定，slow 指針每次前進(jìn) 1 個(gè)節(jié)點(diǎn)，fast 指針每次前進(jìn)兩個(gè)節(jié)點(diǎn)。
（3）當(dāng) slow 與 fast 相等，且二者均不為空，則鏈表存在環(huán)。
無環(huán)過程：
通過圖解過程可以看出，若表中不存在環(huán)形，fast 與 slow 指針只能在鏈表末尾相遇。
有環(huán)過程：
圖解過程可以看出，若鏈表中存在環(huán)，則快慢指針必然能在環(huán)中相遇。這就好比在環(huán)形跑道中進(jìn)行龜兔賽跑。由于兔子速度大于烏龜速度，則必然會(huì)出現(xiàn)兔子與烏龜再次相遇情況。因此，當(dāng)出現(xiàn)快慢指針相等時(shí)，且二者不為NULL，則表明鏈表存在環(huán)。
bool isExistLoop(ListNode* pHead) {
ListNode* fast;//慢指針，每次前進(jìn)一個(gè)節(jié)點(diǎn)
ListNode* slow;//快指針，每次前進(jìn)2個(gè)節(jié)點(diǎn)
slow = fast = pHead ; //兩個(gè)指針均指向鏈表頭節(jié)點(diǎn)
//當(dāng)沒有到達(dá)鏈表結(jié)尾，則繼續(xù)前進(jìn)
while (slow != NULL && fast -> next != NULL) {
slow = slow -> next ; //慢指針前進(jìn)一個(gè)節(jié)點(diǎn)
fast = fast -> next -> next ; //快指針前進(jìn)兩個(gè)節(jié)點(diǎn)
if (slow == fast) //若兩個(gè)指針相遇，且均不為NULL則存在環(huán)
return true ;
}
//到達(dá)末尾仍然沒有相遇，則不存在環(huán)
return false ;
}
在 3.1 節(jié)中，已經(jīng)實(shí)現(xiàn)了鏈表中是否有環(huán)的判斷方法。那么，當(dāng)鏈表中存在環(huán)，如何確定環(huán)的入口節(jié)點(diǎn)呢？
slow 指針每次前進(jìn)一個(gè)節(jié)點(diǎn)，故 slow 與 fast 相遇時(shí)，slow 還沒有遍歷完整個(gè)鏈表。設(shè) slow 走過節(jié)點(diǎn)數(shù)為 s，fast 走過節(jié)點(diǎn)數(shù)為 2s。設(shè)環(huán)入口點(diǎn)距離頭節(jié)點(diǎn)為 a，slow 與 fast 首次相遇點(diǎn)距離入口點(diǎn)為 b，環(huán)的長度為 r。
則有：
s = a + b;
2s = n * r + a + b; n 代表fast指針已經(jīng)在環(huán)中循環(huán)的圈數(shù)。
則推出：
s = n * r; 意味著slow指針走過的長度為環(huán)的長度整數(shù)倍。
若鏈表頭節(jié)點(diǎn)到環(huán)的末尾節(jié)點(diǎn)度為 L，slow 與 fast 的相遇節(jié)點(diǎn)距離環(huán)入口節(jié)點(diǎn)為 X。
則有：
a+X = s = n * r = (n - 1) * r + (L - a);
a = (n - 1) * r + (L - a - X);
上述等式可以看出：
從 slow 與 fast 相遇點(diǎn)出發(fā)一個(gè)指針 p1，請進(jìn) (L - a - X) 步，則此指針到達(dá)入口節(jié)點(diǎn)。同時(shí)指針 p2 從頭結(jié)點(diǎn)出發(fā)，前進(jìn) a 步。當(dāng) p1 與 p2 相遇時(shí)，此時(shí) p1 與 p2 均指向入口節(jié)點(diǎn)。
例如圖3.1所示鏈表：
slow 走過節(jié)點(diǎn) s = 6；
fast 走過節(jié)點(diǎn) 2s = 12；
環(huán)入口節(jié)點(diǎn)據(jù)流頭節(jié)點(diǎn) a = 3；
相遇點(diǎn)距離頭節(jié)點(diǎn) X = 3；
L = 8；
r = 6；
可以得出 a = (n - 1) * r + (L - a - X)結(jié)果成立。
//找到環(huán)中的相遇節(jié)點(diǎn)
ListNode* getMeetingNode(ListNode* pHead) // 假設(shè)為帶頭節(jié)點(diǎn)的單鏈表
{
ListNode* fast;//慢指針，每次前進(jìn)一個(gè)節(jié)點(diǎn)
ListNode* slow;//快指針，每次前進(jìn)2個(gè)節(jié)點(diǎn)
slow = fast = pHead ; //兩個(gè)指針均指向鏈表頭節(jié)點(diǎn)
//當(dāng)沒有到達(dá)鏈表結(jié)尾，則繼續(xù)前進(jìn)
while (slow != NULL && fast -> next != NULL){
slow = slow -> next ; //慢指針前進(jìn)一個(gè)節(jié)點(diǎn)
fast = fast -> next -> next ; //快指針前進(jìn)兩個(gè)節(jié)點(diǎn)
if (slow == fast) //若兩個(gè)指針相遇，且均不為NULL則存在環(huán)
return slow;
}
//到達(dá)末尾仍然沒有相遇，則不存在環(huán)
return NULL ;
}
//找出環(huán)的入口節(jié)點(diǎn)
ListNode* getEntryNodeOfLoop(ListNode* pHead){
ListNode* meetingNode = getMeetingNode(pHead); // 先找出環(huán)中的相遇節(jié)點(diǎn)
if (meetingNode == NULL)
return NULL;
ListNode* p1 = meetingNode;
ListNode* p2 = pHead;
while (p1 != p2) // p1和p2以相同的速度向前移動(dòng)，當(dāng)p2指向環(huán)的入口節(jié)點(diǎn)時(shí)，p1已經(jīng)圍繞著環(huán)走了n圈又回到了入口節(jié)點(diǎn)。
{
p1 = p1->next;
p2 = p2->next;
}
//返回入口節(jié)點(diǎn)
return p1;
}
在3.1中找到了 slow 與 fast 的相遇節(jié)點(diǎn)，令 solw 與 fast 指針從相遇節(jié)點(diǎn)出發(fā)，按照之前的前進(jìn)規(guī)則，當(dāng) slow 與fast 再次相遇時(shí)，slow 走過的長度正好為環(huán)的長度。
int getLoopLength(ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
while ( fast && fast->next ){
slow = slow->next;
fast = fast->next->next;
if ( slow == fast )//第一次相遇
break;
}
//slow與fast繼續(xù)前進(jìn)
slow = slow->next;
fast = fast->next->next;
int length = 1; //環(huán)長度
while ( fast != slow )//再次相遇
{
slow = slow->next;
fast = fast->next->next;
length ++; //累加
}
//當(dāng)slow與fast再次相遇，得到環(huán)長度
return length;
}
兩個(gè)用鏈表代表的整數(shù)，其中每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)字。數(shù)字存儲(chǔ)按照在原來整數(shù)中相反的順序，使得第一個(gè)數(shù)字位于鏈表的開頭。寫出一個(gè)函數(shù)將兩個(gè)整數(shù)相加，用鏈表形式返回和。
例如：
輸入：
3->1->5->null
5->9->2->null，
輸出：
8->0->8->null
ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
ListNode *ret = l1, *pre = l1;
int up = 0;
while (l1 != NULL && l2 != NULL) {
//數(shù)值相加
l1->val = l1->val + l2->val + up;
//計(jì)算是否有進(jìn)位
up = l1->val / 10;
//保留計(jì)算結(jié)果的個(gè)位
l1->val %= 10;
//記錄當(dāng)前節(jié)點(diǎn)位置
pre = l1;
//同時(shí)向后移位
l1 = l1->next;
l2 = l2->next;
}
//若l1到達(dá)末尾，說明l1長度小于l2
if (l1 == NULL)
//pre->next指向l2的當(dāng)前位置
pre->next = l2;
//l1指針指向l2節(jié)點(diǎn)當(dāng)前位置
l1 = pre->next;
//繼續(xù)計(jì)算剩余節(jié)點(diǎn)
while (l1 != NULL) {
l1->val = l1->val + up;
up = l1->val / 10;
l1->val %= 10;
pre = l1;
l1 = l1->next;
}
//最高位計(jì)算有進(jìn)位，則新建一個(gè)節(jié)點(diǎn)保留最高位
if (up != 0) {
ListNode *tmp = new ListNode(up);
pre->next = tmp;
}
//返回計(jì)算結(jié)果鏈表
return ret;
}
題目：將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例：
輸入：
1->2->4,
1->3->4
輸出：
1->1->2->3->4->4
（1）對(duì)空鏈表存在的情況進(jìn)行處理，假如 pHead1 為空則返回 pHead2 ，pHead2 為空則返回 pHead1。（兩個(gè)都為空此情況在pHead1為空已經(jīng)被攔截）
（2）在兩個(gè)鏈表無空鏈表的情況下確定第一個(gè)結(jié)點(diǎn)，比較鏈表1和鏈表2的第一個(gè)結(jié)點(diǎn)的值，將值小的結(jié)點(diǎn)保存下來為合并后的第一個(gè)結(jié)點(diǎn)。并且把第一個(gè)結(jié)點(diǎn)為最小的鏈表向后移動(dòng)一個(gè)元素。
（3）繼續(xù)在剩下的元素中選擇小的值，連接到第一個(gè)結(jié)點(diǎn)后面，并不斷next將值小的結(jié)點(diǎn)連接到第一個(gè)結(jié)點(diǎn)后面，直到某一個(gè)鏈表為空。
（4）當(dāng)兩個(gè)鏈表長度不一致時(shí)，也就是比較完成后其中一個(gè)鏈表為空，此時(shí)需要把另外一個(gè)鏈表剩下的元素都連接到第一個(gè)結(jié)點(diǎn)的后面。
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* pTail = NULL;//指向新鏈表的最后一個(gè)結(jié)點(diǎn) pTail->next去連接
ListNode* newHead = NULL;//指向合并后鏈表第一個(gè)結(jié)點(diǎn)
if (NULL == pHead1){
return pHead2;
}else if(NULL == pHead2){
return pHead1;
}else{
//確定頭指針
if ( pHead1->data < phead2->data){
newHead = pHead1;
pHead1 = pHead1->next;//指向鏈表的第二個(gè)結(jié)點(diǎn)
}else{
newHead = pHead2;
pHead2 = pHead2->next;
}
pTail = newHead;//指向第一個(gè)結(jié)點(diǎn)
while ( pHead1 && pHead2) {
if ( pHead1->data <= phead2->data ){
pTail->next = pHead1;
pHead1 = pHead1->next;
}else {
pTail->next = pHead2;
pHead2 = pHead2->next;
}
pTail = pTail->next;
}
if(NULL == pHead1){
pTail->next = pHead2;
}else if(NULL == pHead2){
pTail->next = pHead1;
}
return newHead;
}
（1）對(duì)空鏈表存在的情況進(jìn)行處理，假如 pHead1 為空則返回 pHead2 ，pHead2 為空則返回 pHead1。
（2）比較兩個(gè)鏈表第一個(gè)結(jié)點(diǎn)的大小，確定頭結(jié)點(diǎn)的位置
（3）頭結(jié)點(diǎn)確定后，繼續(xù)在剩下的結(jié)點(diǎn)中選出下一個(gè)結(jié)點(diǎn)去鏈接到第二步選出的結(jié)點(diǎn)后面，然后在繼續(xù)重復(fù)（2 ）（3） 步，直到有鏈表為空。
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* newHead = NULL;
if (NULL == pHead1){
return pHead2;
}else if(NULL ==pHead2){
return pHead2;
}else{
if (pHead1->data < phead2->data){
newHead = pHead1;
newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
}else{
newHead = pHead2;
newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
}
return newHead;
}
}
給定一個(gè)單鏈表中的表頭和一個(gè)等待被刪除的節(jié)點(diǎn)。請?jiān)?O(1) 時(shí)間復(fù)雜度刪除該鏈表節(jié)點(diǎn)。并在刪除該節(jié)點(diǎn)后，返回表頭。
示例：
給定 1->2->3->4，和節(jié)點(diǎn) 3，返回 1->2->4。
在之前介紹的單鏈表刪除節(jié)點(diǎn)中，最普通的方法就是遍歷鏈表，復(fù)雜度為O(n)。
如果我們把刪除節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的值賦值給要?jiǎng)h除的結(jié)點(diǎn)，然后刪除這個(gè)結(jié)點(diǎn)，這相當(dāng)于刪除了需要?jiǎng)h除的那個(gè)結(jié)點(diǎn)。因?yàn)槲覀兒苋菀撰@取到刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，所以復(fù)雜度只需要O(1)。
示例
單鏈表：1->2->3->4->NULL
若要?jiǎng)h除節(jié)點(diǎn) 3 。第一步將節(jié)點(diǎn)3的下一個(gè)節(jié)點(diǎn)的值4賦值給當(dāng)前節(jié)點(diǎn)。變成 1->2->4->4->NULL，然后將就 4 這個(gè)結(jié)點(diǎn)刪除，就達(dá)到目的了。 1->2->4->NULL
如果刪除的節(jié)點(diǎn)的是頭節(jié)點(diǎn)，把頭結(jié)點(diǎn)指向 NULL。
如果刪除的節(jié)點(diǎn)的是尾節(jié)點(diǎn)，那只能從頭遍歷到頭節(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)。
void deleteNode(ListNode **pHead, ListNode* pDelNode) {
if(pDelNode == NULL)
return;
if(pDelNode->next != NULL){
ListNode *pNext = pDelNode->next;
//下一個(gè)節(jié)點(diǎn)值賦給待刪除節(jié)點(diǎn)
pDelNode->val = pNext->val;
//待刪除節(jié)點(diǎn)指針指后面第二個(gè)節(jié)點(diǎn)
pDelNode->next = pNext->next;
//刪除待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
delete pNext;
pNext = NULL;
}else if(*pHead == pDelNode)//刪除的節(jié)點(diǎn)是頭節(jié)點(diǎn)
{
delete pDelNode;
pDelNode= NULL;
*pHead = NULL;
} else//刪除的是尾節(jié)點(diǎn)
{
ListNode *pNode = *pHead;
while(pNode->next != pDelNode) {
pNode = pNode->next;
}
pNode->next = NULL;
delete pDelNode;
pDelNode= NULL;
}
}
輸入一個(gè)鏈表，按鏈表值從尾到頭的順序返回一個(gè) ArrayList 。
初看題目意思就是輸出的時(shí)候鏈表尾部的元素放在前面，鏈表頭部的元素放在后面。這不就是 先進(jìn)后出，后進(jìn)先出 么。
什么數(shù)據(jù)結(jié)構(gòu)符合這個(gè)要求？
棧 ！
class Solution {
public:
vectorint> printListFromTailToHead(ListNode* head) {
vectorint> value;
ListNode *p=NULL;
p=head;
stackint> stk;
while(p!=NULL){
stk.push(p->val);
p=p->next;
}
while(!stk.empty()){
value.push_back(stk.top());
stk.pop();
}
return value;
}
};
第二種方法也比較容易想到，通過鏈表的構(gòu)造，如果將末尾的節(jié)點(diǎn)存儲(chǔ)之后，剩余的鏈表處理方式還是不變，所以可以使用遞歸的形式進(jìn)行處理。
class Solution {
public:
vectorint> value;
vectorint> printListFromTailToHead(ListNode* head) {
ListNode *p=NULL;
p=head;
if(p!=NULL){
if(p->next!=NULL){
printListFromTailToHead(p->next);
}
value.push_back(p->val);
}
return value;
}
};
反轉(zhuǎn)一個(gè)單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？
設(shè)置三個(gè)節(jié)點(diǎn)pre、cur、next
（1）每次查看cur節(jié)點(diǎn)是否為NULL，如果是，則結(jié)束循環(huán)，獲得結(jié)果
（2）如果cur節(jié)點(diǎn)不是為NULL，則先設(shè)置臨時(shí)變量next為cur的下一個(gè)節(jié)點(diǎn)
（3）讓cur的下一個(gè)節(jié)點(diǎn)變成指向pre，而后pre移動(dòng)cur，cur移動(dòng)到next
（4）重復(fù)（1）（2）（3）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 遞歸終止條件
if(head == NULL || head->next == NULL)
return head;
ListNode* rhead = reverseList(head->next);
// head->next此刻指向head后面的鏈表的尾節(jié)點(diǎn)
// head->next->next = head把head節(jié)點(diǎn)放在了尾部
head->next->next = head;
head->next = NULL;
return rhead;
}
};
聯(lián)系客服
