【一刷《剑指Offer》】面试题 16:反转链表

简介: 【一刷《剑指Offer》】面试题 16:反转链表

力扣对应题目链接:206. 反转链表 - 力扣(LeetCode)

牛客对应题目链接:反转链表_牛客题霸_牛客网 (nowcoder.com)

核心考点 :链表操作,思维缜密程度。


一、《剑指 Offer》内容


二、分析题目

解题思路(有较多解法):

  1. 定义三个指针,整体右移,边移动,边翻转,保证不会断链。
  2. 可以采用头插思想进行翻转。
  3. 递归。递归版本稍微复杂一些,其关键在于反向工作。假设链表的其余部分已经被反转,现在应该如何反转它前面的部分?假设链表为:n_1→…→n_k−1→n_k→n_k+1→…→n_m→∅
    若从节点 n_k+1 到 n_m 已经被反转,而我们正处于 n_k 。
    n_1→…→n_k−1→n_k→n_k+1←…←n_m
    我们希望 n_k+1 的下一个节点指向 n_k。

    所以,n_k->next->next=n_k。
    需要注意的是 n_1 的下一个节点必须指向 ∅。如果忽略了这一点,链表中可能会产生环。

三、代码

1、方法一(三指针)

//牛客AC代码
/**
 * 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* left=head;
        ListNode* mid=head->next;
        ListNode* right=mid->next;
        while(right)
        {
            mid->next=left;
            left=mid;
            mid=right;
            right=right->next;
        }
        mid->next=left;
        head->next=nullptr;
        head=mid;
        return head;
    }
};
 
//力扣AC代码
/**
 * 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* cur=head;
        ListNode* prev=nullptr;
        while(cur)
        {
            ListNode* tmp=cur->next;
            cur->next=prev;
            prev=cur;
            cur=tmp;
        }
        return prev;
    }
};

2、方法二(插入)

//牛客AC代码
/**
 * 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* newHead=nullptr;
        while(head)
        {
            ListNode* p=head;
            head=head->next;
            p->next=newHead;
            newHead=p;
        }
        return newHead;
    }
};
 
//力扣AC代码
/**
 * 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;
        ListNode* newHead=nullptr;
        while(head)
        {
            ListNode* p=head;
            head=head->next;
            p->next=newHead;
            newHead=p;
        }
        return newHead;
    }
};

3、扩展:方法三(递归)

//力扣AC代码(推荐:写法一)
/**
 * 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;
        ListNode* newHead=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return newHead;
    }
};
 
//力扣AC代码(写法二)
/**
 * 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* reverse(ListNode* prev, ListNode* cur)
    {
        if(cur==nullptr) return prev;
        ListNode* tmp=cur->next;
        cur->next=prev;
        return reverse(cur, tmp);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }
};


相关文章
|
25天前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
25天前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
25天前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
25天前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
25天前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
25天前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
25天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
25天前
|
存储 算法 索引
链表面试题
链表面试题
链表面试题
|
25天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
11天前
|
存储 算法 Java
JAVA后端开发面试题库
JAVA后端开发面试题库
19 1