C++怎么實現(xiàn)鏈表重排序
這篇文章主要介紹了C++怎么實現(xiàn)鏈表重排序的相關(guān)知識，內(nèi)容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++怎么實現(xiàn)鏈表重排序文章都會有所收獲，下面我們一起來看看吧。
我們提供的服務(wù)有：網(wǎng)站設(shè)計、成都網(wǎng)站制作、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、光山ssl等。為成百上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的光山網(wǎng)站制作公司
鏈表重排序
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list"s nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
這道鏈表重排序問題可以拆分為以下三個小問題：
1. 使用快慢指針來找到鏈表的中點，并將鏈表從中點處斷開，形成兩個獨立的鏈表。
2. 將第二個鏈翻轉(zhuǎn)。
3. 將第二個鏈表的元素間隔地插入第一個鏈表中。
解法一：
class Solution {
public:
void reorderList(ListNode *head) {
if (!head || !head->next || !head->next->next) return;
ListNode *fast = head, *slow = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *mid = slow->next;
slow->next = NULL;
ListNode *last = mid, *pre = NULL;
while (last) {
ListNode *next = last->next;
last->next = pre;
pre = last;
last = next;
}
while (head && pre) {
ListNode *next = head->next;
head->next = pre;
pre = pre->next;
head->next->next = next;
head = next;
}
}
};我們嘗試著看能否寫法上簡潔一些，上面的第二步是將后半段鏈表翻轉(zhuǎn)，那么我們其實可以借助棧的后進先出的特性來做，如果我們按順序?qū)⑺械慕Y(jié)點壓入棧，那么出棧的時候就可以倒序了，實際上就相當(dāng)于翻轉(zhuǎn)了鏈表。由于只需將后半段鏈表翻轉(zhuǎn)，那么我們就要控制出棧結(jié)點的個數(shù)，還好?？梢灾苯拥玫浇Y(jié)點的個數(shù)，我們減1除以2，就是要出棧結(jié)點的個數(shù)了。然后我們要做的就是將每次出棧的結(jié)點隔一個插入到正確的位置，從而滿足題目中要求的順序，鏈表插入結(jié)點的操作就比較常見了，這里就不多解釋了，最后記得斷開棧頂元素后面的結(jié)點，比如對于 1->2->3->4，棧頂只需出一個結(jié)點4，然后加入原鏈表之后為 1->4->2->3->(4)，因為在原鏈表中結(jié)點3之后是連著結(jié)點4的，雖然我們將結(jié)點4取出插入到結(jié)點1和2之間，但是結(jié)點3后面的指針還是連著結(jié)點4的，所以我們要斷開這個連接，這樣才不會出現(xiàn)環(huán)，由于此時結(jié)點3在棧頂，所以我們直接斷開棧頂結(jié)點即可，參見代碼如下：
解法二：
class Solution {
public:
void reorderList(ListNode *head) {
if (!head || !head->next || !head->next->next) return;
stack<ListNode*> st;
ListNode *cur = head;
while (cur) {
st.push(cur);
cur = cur->next;
}
int cnt = ((int)st.size() - 1) / 2;
cur = head;
while (cnt-- > 0) {
auto t = st.top(); st.pop();
ListNode *next = cur->next;
cur->next = t;
t->next = next;
cur = next;
}
st.top()->next = NULL;
}
};關(guān)于“C++怎么實現(xiàn)鏈表重排序”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“C++怎么實現(xiàn)鏈表重排序”知識都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
本文標(biāo)題：C++怎么實現(xiàn)鏈表重排序
標(biāo)題URL：http://bm7419.com/article26/jddcjg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、微信公眾號、ChatGPT、網(wǎng)頁設(shè)計公司、用戶體驗、做網(wǎng)站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
