您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C++怎么實現(xiàn)成對交換節(jié)點”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“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é)點”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關內(nèi)容可以進入相關頻道進行查詢,關注我們,繼續(xù)學習!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。