【链表】Leetcode 重排链表

这篇具有很好参考价值的文章主要介绍了【链表】Leetcode 重排链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目讲解

143. 重排链表
【链表】Leetcode 重排链表,LeetCode,链表,leetcode


算法讲解

1.使用快慢指针将链表分成两部分 2.将后半部分的链表逆置 3.使用双指针将连个链表分别连接结点在一起文章来源地址https://www.toymoban.com/news/detail-860770.html

/**
 * 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:
    void reorderList(ListNode* head) {
        //找到链表的中间节点  逆置后半部分链表
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)return;
        ListNode* slow = head;
        ListNode* fast = slow->next;
        //寻找中间节点
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //走到这里slow指向的是中间节点的前一个结点  fast指向的是后半部分链表的最后一个节点
        //逆置后半部分链表
        ListNode* newhead = new ListNode(-1);
        ListNode* cur = slow->next;
        slow->next = nullptr; //断开两个部分的链表

        //这一种头插法比较实用
        while(cur)
        {
            ListNode* NextNode = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = NextNode;
        }

        //合并链表
        ListNode* retHead = new ListNode(-1);
        ListNode* cur2 = head;
        cur = newhead->next;
        ListNode* phead = retHead;
        while(cur2)
        {
            phead->next = cur2;
            cur2 = cur2->next;
            phead = phead->next;
            if(cur)
            {
                phead->next = cur;
                cur = cur->next;
                phead = phead->next;
            }
        }
        delete retHead;
        delete newhead;
    }
};

到了这里,关于【链表】Leetcode 重排链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-07-31 LeetCode每日一题(重排链表)

    点击跳转到题目位置 给定一个单链表 L 的头节点 head ,单链表 L 表示为: 请将其重新排列后变为: 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: 示例 2: 提示: 链表的长度范围为 [1, 5 * 10 4 ] 1 = node.val = 1000 (1) 使用 分治 的思路来解决问题。

    2024年02月14日
    浏览(45)
  • leetcode 面试题 判定是否互为字符重排

    🌟 leetcode链接:判定是否互为字符重排 思路: 两个字符串的每个字母和数量都相等。那么 s2 一定可以排成 s1 字符串。 代码:

    2024年02月16日
    浏览(32)
  • LeetCode 面试题 01.02. 判定是否互为字符重排

    ​   给定两个由小写字母组成的字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串,点击此处跳转。 示例 1: 输入: s1 = “abc”, s2 = “bca” 输出: true 示例 2: 输入: s1 = “abc”, s2 = “bad” 输出: false 说明: 0 = len(s1) = 100 0

    2024年02月12日
    浏览(38)
  • 代码随想录第三天|链表理论基础,LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表

    链表: 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是head。 链表类型: 1.单链表 单链表中的指

    2024年02月11日
    浏览(49)
  • 代码随想录第四天|LeetCode24. 两两交换链表中的节点,LeetCode19.删除链表的倒数第N个节点,LeetCode面试题 02.07. 链表相交,LeetCode142.环形链表II

    LeetCode24. 两两交换链表中的节点 题目链接:24. 两两交换链表中的节点 - 力扣(LeetCode) 思路: 先定义一个虚拟头结点方便操作。 再就是交换相邻两个元素了, 此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序 初始时,cur指向虚拟头结点,然后进行

    2024年02月09日
    浏览(37)
  • LeetCode 链表类、输出链表

    这里给出的两个类是在刷力扣时的链表辅助类: ListNode 链表节点类 ListNodeMgr 链表管理类(输出链表元素) ListNode ListNodeMgr

    2024年02月11日
    浏览(29)
  • 刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

    本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解 参与链接在此 : https://programmercarl.com/other/xunlianying.html 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个

    2023年04月09日
    浏览(50)
  • 【leetcode100-033】【链表】排序链表

    【题干】 给你链表的头结点  head  ,请将其按  升序  排列并返回  排序后的链表  。 【思路】 递归版归并法链表版~没什么特别好说的(非递归版归并也是可以哒,但是马上要考试了今天懒得写了!打个flag在这里也许哪天想起来会补写一下) 首先是分割,这一步在链表

    2024年01月24日
    浏览(45)
  • 链表练习 Leetcode234.回文链表

     题目传送门:Leetcode234 给你一个单链表的头节点  head  ,请你判断该链表是否为回文链表。如果是,返回  true  ;否则,返回  false  。 示例 1: 示例 2: 提示: 链表中节点数目在范围 [1, 105]  内 0 = Node.val = 9 进阶: 你能否用  O(n)  时间复杂度和  O(1)  空间复杂度解决

    2024年01月19日
    浏览(40)
  • LeetCode 160.相交链表

    题目链接 👉 LeetCode 160.相交链表👈 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 判断尾节点是否相等,如果尾节点相等就是相交 🍄思路1 A链表所有节点跟B链表都比较一遍,相等的那个就是

    2024年02月12日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包