(链表) 143. 重排链表 ——【Leetcode每日一题】

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

❓143. 重排链表

难度:中等

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L 0 L_0 L0 L 1 L_1 L1 → … → L n − 1 L_{n-1} Ln1 L n L_n Ln

请将其重新排列后变为:

L 0 L_0 L0 L n L_n Ln L 1 L_1 L1 L n − 1 L_{n-1} Ln1 L 2 L_2 L2 L n − 2 L_{n-2} Ln2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

(链表) 143. 重排链表 ——【Leetcode每日一题】

输入:head = [1,2,3,4]
输出:[1,4,2,3]

示例 2:

(链表) 143. 重排链表 ——【Leetcode每日一题】

输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]

提示

  • 链表的长度范围为 [ 1 , 5 ∗ 1 0 4 ] [1, 5 * 10^4] [1,5104]
  • 1 < = n o d e . v a l < = 1000 1 <= node.val <= 1000 1<=node.val<=1000

💡思路:寻找链表中点 + 链表逆序 + 合并链表

  1. 使用 快慢指针 寻找链表中点,将链表分割成两个链表;
  2. 然后把第二个链表利用 头插法 反转;
  3. 之后在通过两个链表拼接成新的链表,将第二个链表插到第一个链表。

🍁代码:(Java、C++)

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 void reorderList(ListNode head) {
        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null){//找到中间节点
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;//后半部分的第一个
        if(fast == null) return;
        slow.next = null;//截断为两部分

        //将后半部分头插法进行重排序
        ListNode h = fast;
        fast = h.next;
        h.next = null;
        while(fast != null){
            slow = fast;
            fast = fast.next;
            slow.next = h;
            h = slow;
        }
        
        //前后两部分合并
        slow = head;//指向前半部分
        fast = h;//指向后半部分
        while(fast != null){//将后半部分插入到前半部分
            fast = fast.next;
            h.next = slow.next;
            slow.next = h;
            slow = h.next;
            h = fast;
        }
    }
}

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:
    void reorderList(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;//后半部分的第一个
        if(fast == nullptr) return;
        slow->next = nullptr;//截断为两部分
        
        //将后半部分头插法进行重排序
        ListNode* h = fast;
        fast = h->next;
        h->next = nullptr;
        while(fast != nullptr){
            slow = fast;
            fast = fast->next;
            slow->next = h;
            h = slow;
        }
        
        //前后两部分合并
        slow = head;
        fast = h;
        while(fast != nullptr){
            fast = fast->next;
            h->next = slow->next;
            slow->next = h;
            slow = h->next;
            h = fast;
        }
    }
};
🚀 运行结果:

(链表) 143. 重排链表 ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n ) O(n) O(n),其中 n 是链表中的节点数。
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-481048.html

注: 如有不足,欢迎指正!

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

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

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

相关文章

  • (链表专题) 725. 分隔链表 ——【Leetcode每日一题】

    给你一个头结点为 head 的单链表和一个整数 k ,请你设计一个算法将链表分隔为 k 个连续的部分。 每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。 这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长

    2023年04月17日
    浏览(43)
  • ( 链表) 203. 移除链表元素 ——【Leetcode每日一题】

    难度:简单 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 提示:

    2024年02月06日
    浏览(72)
  • Leetcode-每日一题【206.反转链表】

    给你单链表的头节点  head  ,请你反转链表,并返回反转后的链表。 示例 1: 输入: head = [1,2,3,4,5] 输出: [5,4,3,2,1] 示例 2: 输入:head = [1,2] 输出:[2,1] 示例 3: 输入:head = [] 输出:[] 提示: 链表中节点的数目范围是 [0, 5000] -5000 = Node.val = 5000   1.我们遍历链表,首先设置

    2024年02月12日
    浏览(37)
  • Leetcode-每日一题【61.旋转链表】

    给你一个链表的头节点  head  ,旋转链表,将链表每个节点向右移动  k   个位置。 示例 1: 输入:head = [1,2,3,4,5], k = 2 输出:[4,5,1,2,3] 示例 2:   输入: head = [0,1,2], k = 4 输出: [2,0,1] 提示: 链表中节点的数目在范围  [0, 500]  内 -100 = Node.val = 100 0 = k = 2 * 109 1.根据题目给出

    2024年02月11日
    浏览(36)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(49)
  • 【LeetCode】每日一题:链表部分经典题型

    ​👻内容专栏:《LeetCode刷题专栏》 🐨本文概括: 归纳链表部分经典题型 。 206.反转链表 、 876.链表的中间节点 、 21.合并两个有序链表 、 160.相交链表 、 141.环形链表 、 142.环形链表Ⅱ 🐼本文作者:花 碟 🐸发布时间:2023.5.17 👉 206.反转链表 题目描述:给你单链表的头

    2024年02月05日
    浏览(39)
  • Leetcode-每日一题【1669.合并两个链表】

    给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。 请你将 list1 中下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。 下图中蓝色边和节点展示了操作后的结果:   请你返回结果链表的头指针。 示例 1: 输入: list1 = [0,1,2,3,4,5], a = 3, b

    2024年02月13日
    浏览(49)
  • 2023-07-29 LeetCode每日一题(环形链表)

    点击跳转到题目位置 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:p

    2024年02月15日
    浏览(42)
  • 链表专题1—24. 两两交换链表中的节点 234.回文链表 143.重排链表 141.环形链表 142.环形链表II 160.链表相交 C++实现

    迭代法,时间复杂度: O ( n ) O(n) O ( n ) , 空间复杂度: O ( 1 ) O(1) O ( 1 ) 时间复杂度、空间复杂度: O ( n ) O(n) O ( n ) 止位置时,慢指针就在链表中间位置。 同时用pre记录慢指针指向节点的前一个节点,用来分割链表,将链表分为前后均等两部分,如果链表长度是奇数,那么

    2024年02月12日
    浏览(45)
  • Leetcode-每日一题【147.对链表进行插入排序】

    给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。 插入排序 算法的步骤: 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在

    2024年02月16日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包