?劍指 Offer 24. 反轉(zhuǎn)鏈表

難度：簡(jiǎn)單

定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

限制：

• 0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000

注意：本題與 206. 反轉(zhuǎn)鏈表 相同。

??思路：

法一：遞歸

可以將本問題分解成子問題：

• 1->(剩余部分的反轉(zhuǎn))，而1 始終指向 2，即1->2
• 所以第一層遞歸的結(jié)果以為： 5->4->3->2 <-1
• 每一層以此類推。

法二：迭代

• 頭插法。

??代碼：(C++、Java)

法一：遞歸
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* temp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return temp;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

法二：迭代
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* h0 = new ListNode(-1);
        ListNode* temp = head;
        while(head != nullptr){
            head = head->next;
            temp->next = h0->next;
            h0->next = temp;
            temp = head;
        }
        head = h0->next;
        delete(h0);
        return head;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode h0 = new ListNode(-1);
        ListNode temp = head;
        while(head != null){
            head = head.next;
            temp.next = h0.next;
            h0.next = temp;
            temp = head;
        }
        head = h0.next;
        return head;
    }
}

?? 運(yùn)行結(jié)果：

?? 復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$，其中 n 為鏈表的長(zhǎng)度。
• 空間復(fù)雜度：$O(1)$，遞歸空間復(fù)雜度為$O(n)$，主要取決于遞歸調(diào)用的?？臻g，最多為 n 層。而迭代只需要常數(shù)級(jí)額外空間，即為 $O(1)$。

題目來源：力扣。

放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁(yè) / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-607293.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于(鏈表) 劍指 Offer 24. 反轉(zhuǎn)鏈表 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！