C++实现LeetCode(143.链表重排序)

[LeetCode] 143.Reorder List 链表重排序

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

这道链表重排序问题可以拆分为以下三个小问题：

1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。

2. 将第二个链翻转。

3. 将第二个链表的元素间隔地插入第一个链表中。

解法一：

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = NULL;
        ListNode *last = mid, *pre = NULL;
        while (last) {
            ListNode *next = last->next;
            last->next = pre;
            pre = last;
            last = next;
        }
        while (head && pre) {
            ListNode *next = head->next;
            head->next = pre;
            pre = pre->next;
            head->next->next = next;
            head = next;
        }
    }
};

我们尝试着看能否写法上简洁一些，上面的第二步是将后半段链表翻转，那么我们其实可以借助栈的后进先出的特性来做，如果我们按顺序将所有的结点压入栈，那么出栈的时候就可以倒序了，实际上就相当于翻转了链表。由于只需将后半段链表翻转，那么我们就要控制出栈结点的个数，还好栈可以直接得到结点的个数，我们减1除以2，就是要出栈结点的个数了。然后我们要做的就是将每次出栈的结点隔一个插入到正确的位置，从而满足题目中要求的顺序，链表插入结点的操作就比较常见了，这里就不多解释了，最后记得断开栈顶元素后面的结点，比如对于 1->2->3->4，栈顶只需出一个结点4，然后加入原链表之后为 1->4->2->3->(4)，因为在原链表中结点3之后是连着结点4的，虽然我们将结点4取出插入到结点1和2之间，但是结点3后面的指针还是连着结点4的，所以我们要断开这个连接，这样才不会出现环，由于此时结点3在栈顶，所以我们直接断开栈顶结点即可，参见代码如下：

解法二：

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        stack<ListNode*> st;
        ListNode *cur = head;
        while (cur) {
            st.push(cur);
            cur = cur->next;
        }
        int cnt = ((int)st.size() - 1) / 2;
        cur = head;
        while (cnt-- > 0) {
            auto t = st.top(); st.pop();
            ListNode *next = cur->next;
            cur->next = t;
            t->next = next;
            cur = next;
        }
        st.top()->next = NULL;
    }
};

参考资料：

https://leetcode.com/problems/reorder-list/

https://leetcode.com/problems/reorder-list/discuss/45175/Java-solution-with-stack

https://leetcode.com/problems/reorder-list/discuss/44992/Java-solution-with-3-steps

到此这篇关于C++实现LeetCode(143.链表重排序)的文章就介绍到这了,更多相关C++实现链表重排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(104.二叉树的最大深度)

    [LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child

  • C++实现LeetCode(106.由中序和后序遍历建立二叉树)

    [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树 Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given ino

  • C++实现LeetCode(889.由先序和后序遍历建立二叉树)

    [LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和后序遍历建立二叉树 Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals pre and post are distinct positive integers. Example 1

  • C++实现LeetCode(103.二叉树的之字形层序遍历)

    [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example

  • C++实现LeetCode(142.单链表中的环之二)

    C++实现LeetCode(142.单链表中的环之二)

    [LeetCode] 142. Linked List Cycle II 单链表中的环之二 Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexe

  • C++实现LeetCode(108.将有序数组转为二叉搜索树)

    [LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary

  • C++实现LeetCode(105.由先序和中序遍历建立二叉树)

    [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preor

  • C++实现LeetCode(143.链表重排序)

    [LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 常见排序方法有

  • 详解C++实现链表的排序算法

    详解C++实现链表的排序算法

    一.链表排序 最简单.直接的方式(直接采用冒泡或者选择排序,而且不是交换结点,只交换数据域) //线性表的排序,采用冒泡排序,直接遍历链表 void Listsort(Node* & head) { int i = 0; int j = 0; //用于变量链表 Node * L = head; //作为一个临时量 Node * p; Node * p1; //如果链表为空直接返回 if (head->value == 0)return; for (i = 0; i < head->

  • JAVA中JVM的重排序详细介绍

    在并发程序中,程序员会特别关注不同进程或线程之间的数据同步,特别是多个线程同时修改同一变量时,必须采取可靠的同步或其它措施保障数据被正确地修改,这里的一条重要原则是:不要假设指令执行的顺序,你无法预知不同线程之间的指令会以何种顺序执行. 但是在单线程程序中,通常我们容易假设指令是顺序执行的,否则可以想象程序会发生什么可怕的变化.理想的模型是:各种指令执行的顺序是唯一且有序的,这个顺序就是它们被编写在代码中的顺序,与处理器或其它因素无关,这种模型被称作顺序一致性模型,也是基于冯·诺依曼体系的模型.

  • 浅谈java指令重排序的问题

    指令重排序是个比较复杂.觉得有些不可思议的问题,同样是先以例子开头(建议大家跑下例子,这是实实在在可以重现的,重排序的概率还是挺高的),有个感性的认识 /** * 一个简单的展示Happen-Before的例子. * 这里有两个共享变量:a和flag,初始值分别为0和false.在ThreadA中先给 a=1,然后flag=true. * 如果按照有序的话,那么在ThreadB中如果if(flag)成功的话,则应该a=1,而a=a*1之后a仍然为1,下方的if(a==0)应该永远不会为 * 真,

  • JS中数组重排序方法

    1.数组中已存在两个可直接用来重排序的方法:reverse()和sort(). reverse()和sort()方法的返回值是经过排序后的数组.reverse()方法会反转数组项的顺序: var values=[1,2,3,4,5]; values.reverse(); alert(values); //5,4,3,2,1 在默认情况下,sort()方法按升序排列数组,sort()方法会调用每个数组项的toString()转型方法,然后比较得到字符串,确定如何排序.即使数组中的每一项都是数值,s

  • 深入JavaScript高级程序设计之对象、数组（栈方法，队列方法，重排序方法，迭代方法）

    继承是OO语言中的一个最为人津津乐道的概念. 许多OO语言都支持两种继承方式:接口继承和实现继承. 接口继承只继承方法签名,而实现继承则继承实际的方法. 如其所述,由于函数没有签名,在ECMAScript中无法实现接口继承. ECMAScript只支持实现继承,而且其实现继承主要是依靠原型链来实现的. 1.使用对象字面量定义对象 var person={}; 使用这种方式创建对象时,实际上不会调用Object构造函数. 开发人员更喜欢对象字面量的语法. 2.有时候需要传递大量可选参数的情形时,一

  • Android 中ViewPager重排序与更新实例详解

    Android 中ViewPager重排序与更新实例详解 最近的项目中有栏目订阅功能,在更改栏目顺序以后需要更新ViewPager.类似于网易新闻的频道管理. 在重新排序之后调用了PagerAdapter的notifyDataSetChanged方法,发现ViewPager并没有更新,于是我开始跟踪源码,在调用PagerAdapter的notifyDataSetChanged方法后,会触发Viewpager的dataSetChanged方法. void dataSetChanged() { //

  • Array 重排序方法和操作方法的简单实例

    复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml" ><head>    <title>重排序方法和操作

  • Java内存之happens-before和重排序

    Java内存之happens-before和重排序

    happens-before原则规则: 程序次序规则:一个线程内,按照代码顺序,书写在前面的操作先行发生于书写在后面的操作: 锁定规则:一个unLock操作先行发生于后面对同一个锁的lock操作: volatile变量规则:对一个变量的写操作先行发生于后面对这个变量的读操作: 传递规则:如果操作A先行发生于操作B,而操作B又先行发生于操作C,则可以得出操作A先行发生于操作C: 线程启动规则:Thread对象的start()方法先行发生于此线程的每个一个动作: 线程中断规则:对线程interrup

随机推荐