LeetCode_LinkedList_206.反向链接表 Reverse Linked List (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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

二，解题思路

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;
    }
}

四，解题过程

第一博

头插法，当年数据结构老师教的东西还好没丢。

​

第二搏

原地反转

​

第三搏

递归，这个也是新鲜的解法，相比于其他算法可以明显看出递归对于内存的消耗较大

​

​