首页 > 代码库 > LeetCode Solutions : Reorder List
LeetCode Solutions : 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 itto {1,4,2,3}.
Considering the following steps:
* 1. split such list into two list, first and second, according to slow and fast point
* 2. reverse the second list
* 3. insert the second list into the first list
coding solution:
/** * 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){ ListNode low=head;//1. split such list into two list, first and second, according to slow and fast point ListNode fast=head; while(fast.next!=null&&fast.next.next!=null){ low=low.next; fast=fast.next.next; } ListNode first=head; ListNode second=low.next; low.next=null; second=reverse(second);//2. reverse the second list while(second!=null){//3. insert the second list into the first list ListNode p1=first.next; ListNode p2=second.next; first.next=second; second.next=p1; first=p1; second=p2; } } } private ListNode reverse(ListNode head){ if(head==null||head.next==null) return head; ListNode pre=head; ListNode cur=head.next; while(cur!=null){ ListNode nextNode=cur.next; cur.next=pre; pre=cur; cur=nextNode; } head.next=null; return pre; } }
LeetCode Solutions : Reorder List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。