文档章节

143. Reorder List - LeetCode

yysue
 yysue
发布于 07/15 23:39
字数 404
阅读 16
收藏 1

Question

143. Reorder List

Solution

题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表

思路 :先将链表分成前后两部分,将后部分链表反转,再将两部分链表连接成一个新链表

链表取中间节点思路:龟兔赛跑,每秒钟乌龟跑1步,兔子跑2步,当兔子跑完全程时乌龟正好跑完一半

链表反转实现思路 :

Java实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        ListNode mid = findMid(head);
        ListNode l2 = mid.next;
        mid.next = null; // 将前半部分链表截断
        l2 = reverse(l2); // 将后半部分链表反转
        ListNode l1 = head;
        // 组装新的链表
        while (l1 != null && l2 != null) {
            ListNode tmp = l1.next;
            l1.next = l2;
            l2 = l2.next;
            l1.next.next = tmp;
            l1 = tmp;
        }
    }
    
    // 返回链表的中间节点
    // 龟兔赛跑,每秒钟乌龟跑1步,兔子跑2步,当兔子跑完全程时乌龟正好跑完一半
    ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    
    // 返回反转后的链表
    ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}

© 著作权归作者所有

共有 人打赏支持
yysue
粉丝 27
博文 268
码字总数 155357
作品 0
济南
程序员
私信 提问
LeetCode目录。

按照LeetCode的Tags来区分的话,目前共有34个Tag,只列出已经解决的题,各分类中按照题目编号排序: Linked List。 Solved:21/28 Array。

Leafage_M
2017/11/21
0
0
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 must do this in-place without altering the nodes’ values. For example, Giv......

Leafage_M
2017/10/20
0
0
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 must do this in-place without altering the nodes' values. For example, Giv......

什么都没想到
2017/10/27
0
0
Leetcode日记8

(2015/2/3) LeetCode 4 Median of Two Sorted Arrays 题目大意:找到两个已排序数组的median。 median:中间位置的值。 算法: 参考:https://leetcode.com/discuss/15790/share-my-o-log...

fxdhdu
2016/02/18
94
0
143. Reorder List

题目描述:给链表如L: L0→L1→…→Ln-1→Ln,将其重新排序为L0→Ln→L1→Ln-1→L2→Ln-2→…,要求空间复杂度为O(1),且不修改结点的值。 分析:若没有要求,可以先遍历链表在数组中记录每个...

Nautilus1
2017/11/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud 分布式链路跟踪 Sleuth + Zipkin + Elasticsearch

随着业务越来越复杂,系统也随之进行各种拆分,特别是随着微服务架构的兴起,看似一个简单的应用,后台可能很多服务在支撑;一个请求可能需要多个服务的调用;当请求迟缓或不可用时,无法得知...

编程SHA
11分钟前
1
0
Swift-清除缓存

func removeCache (){ // 取出cache文件夹路径.如果清除其他位子的可以将cachesDirectory换成对应的文件夹 let cachePath = NSSearchPathForDirectoriesInDomains(FileMan...

west_zll
11分钟前
1
0
kl键盘事件

frameworks/base/data/keyboards路径下定义了很对kl文件。如Vendor_0416_Product_0300.kl,定义了某某遥控器的按键事件 # TVkey 103 DPAD_UPkey 108 DPAD_DOWNkey 105 DPAD_LEFTk...

安卓工程师王恒
15分钟前
1
0
CentOS 7 安装 Docker

工具: Oracle VM VirtualBox 虚拟机 ,本地电脑win10 系统: 虚拟机装 centos 7 前置条件: Docker 要求 CentOS 系统的内核版本高于 3.10 1. 通过 uname -r 命令查看当前的内核版本 2. 如果不够...

_大侠__
25分钟前
1
0
webrtc onAddStream回调流程

背景 webrtc代码基于M59 正文 1. 回调设置和处理 (1)java层先在监听器中实现回调处理函数,如下所示: private class PCObserver implements PeerConnection.Observer { @Override...

bill_shen
27分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部