您好,登錄后才能下訂單哦!
這篇文章主要講解了“C++如何實現(xiàn)成對交換節(jié)點”,文中的講解內(nèi)容簡單清晰,易于學習與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學習“C++如何實現(xiàn)成對交換節(jié)點”吧!
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list"s nodes, only nodes itself may be changed.
Example:
Given
1->2->3->4
, you should return the list as
2->1->4->3.
這道題不算難,是基本的鏈表操作題,我們可以分別用遞歸和迭代來實現(xiàn)。對于迭代實現(xiàn),還是需要建立 dummy 節(jié)點,注意在連接節(jié)點的時候,最好畫個圖,以免把自己搞暈了,參見代碼如下:
解法一:
class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode *dummy = new ListNode(-1), *pre = dummy; dummy->next = head; while (pre->next && pre->next->next) { ListNode *t = pre->next->next; pre->next->next = t->next; t->next = pre->next; pre->next = t; pre = t->next; } return dummy->next; } };
遞歸的寫法就更簡潔了,實際上利用了回溯的思想,遞歸遍歷到鏈表末尾,然后先交換末尾兩個,然后依次往前交換:
解法二:
class Solution { public: ListNode* swapPairs(ListNode* head) { if (!head || !head->next) return head; ListNode *t = head->next; head->next = swapPairs(head->next->next); t->next = head; return t; } };
解法三:
class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head; return newHead; } }
感謝各位的閱讀,以上就是“C++如何實現(xiàn)成對交換節(jié)點”的內(nèi)容了,經(jīng)過本文的學習后,相信大家對C++如何實現(xiàn)成對交換節(jié)點這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。