首页 > 代码库 > 【LeetCode】Reorder List
【LeetCode】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,
Given {1,2,3,4}
, reorder it to {1,4,2,3}
.
先将链表从中间截成两部分(奇数的前半部分多一,注意截断后最后个元素指向null),然后翻转后半部分的,最后将两部分合并起来即可,代码如下:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public void reorderList(ListNode head) { if(head==null||head.next==null){ return; } ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null&&fast.next.next!=null){ //要获取中间节点的前一个元素 fast=fast.next.next; slow=slow.next; } ListNode halfNode=slow.next; slow.next=null; //注意此处要将前半段最后一个元素指向null ListNode halfHead=null; while(halfNode!=null){ ListNode pre=halfNode; halfNode=halfNode.next; pre.next=halfHead; halfHead=pre; } ListNode cur=head; while(halfHead!=null){ ListNode pre=halfHead; halfHead=halfHead.next; pre.next=cur.next; cur.next=pre; cur=cur.next.next; //注意指针要指向隔一个节点 } } }
---EOF---
【LeetCode】Reorder List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。