LeetCode_LinkedList_206. Reverse Linked List 反轉連結清單（C++/Java）【頭插法，尾插法，遞歸】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​二，解題思路​​

​​1，頭插法​​

​​2，尾插法​​

​​3，遞歸​​

​​出口條件​​

​​如何遞歸​​

​​三，AC代碼​​

​​C++​​

​​頭插法​​

​​尾插法​​

​​遞歸​​

​​Java​​

​​遞歸​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

​​第三搏​​

一，題目描述

英文描述

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]

Output: [2,1]

Example 3:

Input: head = []

Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].

-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

中文描述

給你單連結清單的頭節點 head ，請你反轉連結清單，并傳回反轉後的連結清單。

示例 1：

示例 2：

示例 3：

輸入：head = []

輸出：[]

提示：

連結清單中節點的數目範圍是 [0, 5000]

-5000 <= Node.val <= 5000

進階：連結清單可以選用疊代或遞歸方式完成反轉。你能否用兩種方法解決這道題？

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/reverse-linked-list​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

1，頭插法

換不多說，先上圖

簡單來說，就是不斷将原先連結清單的節點依次插入在虛拟頭節點head和頭節點後面一個節點之間。

2，尾插法

和頭插法類似，但是建立的不是頭節點，而是空節點（尾節點）；

然後不斷将原先連結清單的節點依次連結到新連結清單的頭部即可。

3，遞歸

遞歸的兩大要素：出口，如何遞歸。

出口條件

當傳入的連結清單為空或者隻有一個節點時，因為此時連結清單沒有必要反轉。

如何遞歸

遞歸的核心思想是将連結清單分為兩部分：頭節點，其他節點。

其他節點可以作為一個新的連結清單，繼續調用遞歸函數。也就是說當我們把其他節點組成的連結清單放入函數後，就可以将其看作已經反轉過了。

假設其他節點已經反轉過了，那麼接下來要考慮的就是将頭節點重新接到另一部分連結清單的後面

為了實作上面的做法，需要兩個指針變量：tail（指向反轉部分的尾節點，也就是上圖中的2），h（指向反轉後連結清單的頭節點，也就是上圖中的5）。其中tail=head->next，h=reverseList(head->next)。

後面就比較簡單了，就是将頭節點接到尾節點後面，并且傳回新的頭節點h即可

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 當連結清單為空或者隻有一個節點時 不需要反轉
        if(head == nullptr || head->next == nullptr) return head;
        // 遞歸的核心思想是将連結清單分為兩部分：頭節點、其餘部分節點反轉後的新連結清單
        // 将頭節點接到新連結清單的尾部即可完成算法
        // tail指已反轉部分連結清單的尾部 h指已反轉部分連結清單的頭節點
        ListNode *tail = head->next, *h = reverseList(head->next);
        head->next = tail->next;
        tail->next = head;
        return h;
    }
};      

三，AC代碼

C++

頭插法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *h = new ListNode;// 虛拟頭節點
        if(head == nullptr) return head;
        ListNode *p = head, *q = head->next;
        while(p != nullptr) {
            p->next = h->next;
            h->next = p;
            p = q;
            if(q != nullptr) q = q->next;
        }
        return h->next;
    }
};      

尾插法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newList = nullptr;// 建立新連結清單節點 先指向空
        if(head == nullptr) return head;
        ListNode *p = head, *q = head->next;
        while(p != nullptr) {
            p->next = newList;
            newList = p;
            p = q;
            if(q != nullptr) q = q->next;
        }
        return newList;
    }
};      

遞歸

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 當連結清單為空或者隻有一個節點時 不需要反轉
        if(head == nullptr || head->next == nullptr) return head;
        // 遞歸的核心思想是将連結清單分為兩部分：頭節點、其餘部分節點反轉後的新連結清單
        // 将頭節點接到新連結清單的尾部即可完成算法
        // tail指已反轉部分連結清單的尾部 h指已反轉部分連結清單的頭節點
        ListNode *tail = head->next, *h = reverseList(head->next);
        head->next = tail->next;
        tail->next = head;
        return h;
    }
};      

Java

遞歸

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

四，解題過程

第一博

頭插法，當年資料結構老師教的東西還好沒丢。

第二搏

原地反轉

第三搏