愛悠閑 > Swap Nodes in Pairs ——解題報告

Swap Nodes in Pairs ——解題報告

分類: LeetCode  |  標簽: LeetCode,鏈表,遞歸,反轉  |  作者: puqutogether 相關  |  發布日期 : 2015-05-12  |  熱度 : 0°

    【題目】

    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.


    【分析】

    使用遞歸解決,首先跳出遞歸的條件一定是鏈表剩余長度為0或1,即head == NULL,head->next == NULL. 其次,一定要注意在鏈表還有剩余節點的情況下倒轉兩個節點,不然,head->next都為空了,如何反轉后面節點呢?具體見下面注釋。


    【代碼】

    運行時間4ms


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        if(head == NULL || head->next == NULL)  // 遞歸跳出條件
            return head;
        ListNode* tmp = swapPairs(head->next->next);  //一定要在前面遞歸,如果head->next都為空了,遞歸進去是可以看到的,但是下面直接去head->next就判斷不了。
        ListNode* res = head->next;
        res->next = head;
        res->next->next = tmp;
        return res;
    }
};


快乐彩中奖说明