文档章节

143. Reorder List - LeetCode

yysue
 yysue
发布于 07/15 23:39
字数 404
阅读 6
收藏 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
粉丝 19
博文 217
码字总数 134384
作品 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......

什么都没想到
2017/10/27
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
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
玩转算法面试:(五)LeetCode链表类问题

在链表中穿针引线 链表和数组都是线性结构,但是链表和数组的不同在于数组可以随机的对于数据进行访问。给出索引。可以以O(1)的时间复杂度迅速访问到该元素。 链表只能从头指针开始。 next指...

天涯明月笙
2017/09/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

redis数据结构

1.数据结构 1.1 简单动态字符串 sds struct sdshdr { int len; // buf数组中记录的字符串长度 int free; //bug数组未使用的长度 char buf[]; //字节数组,用于保存字符串...

Funcy1122
40分钟前
0
0
通过ip获取真实地址

package util;import com.alibaba.fastjson.JSON;import com.alibaba.fastjson.JSONObject;import org.apache.commons.lang3.StringUtils;import org.apache.http.HttpResponse;......

lifes77
今天
3
0
解决nginx 出现 413 Request Entity Too Large的问题

php.ini 文件已经设置了附件大小和表单提交大小为128M upload_max_filesize = 128M post_max_size = 128M 然而nginx还是报 413 Request Entity Too Large 错怎么办 打开/etc/nginx/sites-av...

Marhal
今天
1
0
Vue 服务端渲染(SSR)

Vue 服务端渲染(SSR) 什么是服务端渲染,简单理解是将组件或页面通过服务器生成html字符串,再发送到浏览器,最后将静态标记"混合"为客户端上完全交互的应用程序。于传统的SPA(单页应用)...

Jack088
今天
1
0
Java 计算日期间天数与日期推算等操作

package com.yh.emmm.pattern;import java.time.LocalDate;/** * 计算两个日期之间的天数 * * @author 枫茗丿love */public class CountDaysUtils { /** * 两...

yh500
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部