【一刷《剑指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);
    }
};


目录
打赏
0
0
0
0
9
分享
相关文章
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
9月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
107 0
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
|
11月前
|
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
107 5
|
11月前
|
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
98 4
【面试题】合井K个升序链表
【面试题】合井K个升序链表
63 0
【Java集合类面试十】、HashMap中的循环链表是如何产生的?
在多线程环境下,HashMap在扩容时如果发生条件竞争,元素的插入顺序可能形成循环链表,导致死循环。
【剑指offer】2.2编程语言(p22-p25)——面试题1:string赋值运算函数
【剑指offer】2.2编程语言(p22-p25)——面试题1:string赋值运算函数
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问