24. Swap Nodes in Pairs #Linked List (Easy)

Problem:

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space.
You may not modify the values in the list, only nodes itself can be changed.

Solution:

//recursive solution
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* next = head->next;
        head->next = swapPairs(head->next->next); //important
        next->next = head;
        head = next; 
        return head;      
    }
};
// copy
// iterative solution with dummy node
ListNode *swapPairs(ListNode *head) {
    ListNode *dummy = new ListNode(0), *node;
    node = dummy;
    dummy->next = head;
    while (head && head->next) {
        ListNode *nxt = head->next;
        head->next = nxt->next;
        nxt->next = head;
        node->next = nxt;
        node = head;
        head = node->next;
    }
    return dummy->next;
}

LeetCode Discussion

Memo:

Study dummy node.

Recursion need to give some implementation only once, otherwise it will be redundant.

//first version of my recursion code
//works but redundant
ListNode* swapPairs(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    if (head->next->next == NULL) //this part is unnecessary,think why
    {
        ListNode* next = head->next;
        next->next = head;
        head->next = NULL;
        head = next;
    }
    else
    {
        ListNode* next = head->next;
        head->next = swapPairs(head->next->next); //important
        next->next = head;
        head = next;
    }
    return head;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末讶舰,一起剝皮案震驚了整個濱河市睁枕,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件丙唧,死亡現(xiàn)場離奇詭異凿跳,居然都是意外死亡,警方通過查閱死者的電腦和手機战得,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來庸推,“玉大人常侦,你說我怎么就攤上這事”崦剑” “怎么了聋亡?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵,是天一觀的道長际乘。 經(jīng)常有香客問我坡倔,道長,這世上最難降的妖魔是什么脖含? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任罪塔,我火速辦了婚禮,結(jié)果婚禮上养葵,老公的妹妹穿的比我還像新娘征堪。我一直安慰自己,他們只是感情好关拒,可當我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布佃蚜。 她就那樣靜靜地躺著,像睡著了一般着绊。 火紅的嫁衣襯著肌膚如雪谐算。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天归露,我揣著相機與錄音洲脂,去河邊找鬼。 笑死剧包,一個胖子當著我的面吹牛腮考,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播玄捕,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼棚放!你這毒婦竟也來了枚粘?” 一聲冷哼從身側(cè)響起奈梳,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎析命,沒想到半個月后麦备,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡攀圈,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年暴凑,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片赘来。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡现喳,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出犬辰,到底是詐尸還是另有隱情嗦篱,我是刑警寧澤,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布幌缝,位于F島的核電站灸促,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏涵卵。R本人自食惡果不足惜浴栽,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望轿偎。 院中可真熱鬧典鸡,春花似錦、人聲如沸贴硫。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽英遭。三九已至间护,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間挖诸,已是汗流浹背汁尺。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留多律,地道東北人痴突。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像狼荞,于是被迫代替她去往敵國和親辽装。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗相味。 張土汪:刷leetcod...
    土汪閱讀 12,750評論 0 33
  • **2014真題Directions:Read the following text. Choose the be...
    又是夜半驚坐起閱讀 9,595評論 0 23
  • C是“面向過程”的程序設(shè)計語言;C++拓巧,C#斯碌,java是“面向?qū)ο蟆钡某绦蛟O(shè)計語言。舉個例子:比如你想做一個模型飛...
    雅然風(fēng)懿閱讀 862評論 1 4
  • 我的身體里有一只巨大的寄生蟲肛度。而且它越長越大傻唾,最近有瘋長的趨勢,隱隱的感覺我已經(jīng)失去對它的控制承耿。 最初我以為它是一...
    雛菊夢夢閱讀 384評論 0 0
  • 合上《錢商》這本書冠骄,結(jié)局皆大歡喜,告訴我一個事實瘩绒,誠實對待自己猴抹,盡可能公平公正的對待公眾,看清事實并相信自己的...
    dreamingyou閱讀 145評論 0 0