JZ24 反转链表

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤10000≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例1

输入：

{1,2,3}

返回值：

{3,2,1}

示例2

输入：

{}

返回值：

{}

说明：

空链表则输出空                 

题解1

使用栈当做中转站，把每个节点倒过来，然后重新拼成一个新链表

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        if(head == nullptr)
            return head;
        stack<ListNode*> st;
        ListNode* p = head;
        while (p != nullptr) {
            st.push(p);
            p = p->next;
        }
        ListNode* tail = st.top();
        st.pop();
        ListNode* res = tail;
        while (!st.empty()) {
            ListNode* node = st.top();
            st.pop();
            tail->next = node;
            tail = node;
        }
        //最后的节点为原来的头结点，需要将其的下一个节点设为空，否则会构成环
        tail->next = nullptr;
        return res;
    }
};

题目细节

结点3为tail变量，经过while循环，会使用尾插法将结点1和2都插入到3后面，这期间，结点2和3和next指针都经过了处理，而最后一个结点1的next指针（结点1的next原本是指向结点2的）却没有处理，因为此时已经跳出了while循环。如果不将结点1的下一个结点置为空，则会在结点1和2之间形成环，程序输出会如下：

3,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2...

题解2

使用两个结点求解，将摘下来的每一个结点使用头插法插入到新的链表中，如图画了程序两步的情况

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        ListNode* newHead = nullptr;
        while(head!=nullptr){
            ListNode* tmp = head->next;
            head->next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
};

扩展思维

其实用vector容器顺序存放各个结点，然后出来的时候使用头插法新建链表也可以，这样分离结点的时候可能不太容易出错

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        vector<ListNode*> vt;
        while (head != nullptr) {
            //分离结点
            ListNode* tmp = head->next;
            head->next = nullptr;
            vt.push_back(head);
            head = tmp;
        }
        //新建链表
        ListNode* res = nullptr;
        for (auto node : vt) {
            node->next = res;
            res = node;
        }
        return res;
    }
};

同样也可以不使用vector

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        ListNode* res = nullptr;
        // write code here
        while (head != nullptr) {
            ListNode* tmp = head->next;
            head->next = nullptr;
            ListNode* node = head;

            node->next = res;
            res = node;

            head = tmp;
        }
        return res;
    }
};

tip：之前头插法一直记错了，如果头结点没有数据的话，可以使用下面的操作

node->next = head->next;
head->next = node;

但是如果头结点有值，就要用下列的插入

node->next = head；
head = node;

解法3

原地反转，用三个指针逆置

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        if(head == nullptr)
            return head;
        // write code here
        ListNode* p = head->next, *pre = head;
        pre->next = nullptr;//第一个结点的next指针要预先处理，循环只能处理后面结点的next指针
        while(p != nullptr){
            ListNode* tmp = p->next;
            //反转
            p->next = pre;

            pre = p;
            p = tmp;
        }
        return pre;
    }
};

解法4

使用递归解决

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* cur_next = head->next;
        ListNode* newHead = ReverseList(cur_next);
        cur_next->next = head;
        head->next = nullptr;
        return newHead;

    }
};