文档章节

143. Reorder List - LeetCode

yysue
 yysue
发布于 07/15 23:39
字数 404
阅读 9
收藏 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
粉丝 26
博文 264
码字总数 154329
作品 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
nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Qt那些事0.0.7

在帮助文档(Overview - QML and C++ Integration)中随缘遇到一张图,是关于C++对象与QML整合介绍的,值得标记下来,虽然大部分功能也有所涉猎,但是还是留个记号,万一哪天我失忆了还想写Q...

Ev4n
8分钟前
0
0
快速幂运算

题:求一个数 data 的 n 次幂,要求时间复杂度为log(n) 1:递归算法: /** * x^3=(x^2)*x;x^7=(x^3)^2 * x * * 递归算法 * @param data 底数 * @param n 次...

偶尔诗文
12分钟前
0
0
Google 宣布将会关闭消费者版本 Google+

Google 家的社交平台 Google+ 原来曾经在今年 3 月发生了一次严重的用户资料外泄事故,但这科网巨擘却一直保密,直至今天华尔街日报把事件披露之后才确认事件。Google 在重申问题已经即时解决...

问题终结者
25分钟前
0
0
腾讯三大运维开源项目齐聚“OSCAR开源先锋日”

10月20日,腾讯开源三大运维开源项目——TARS、蓝鲸和织云Metis首次集结,参与了由中国信息通信研究院主办、云计算标准与开源推进委员会承办的 “OSCAR开源先锋日”。会上,腾讯开源团队与前...

腾讯开源
30分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部