【Leetcode】Reorder List JAVA

浏览数：24 / 时间：2015年06月08日

一、题目描述

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}.

二、分析

1、暴力解法

这种解法所需的时间的时间复杂度比较高，为O（n2）

代码如下：该代码在Leetcode上提交会提示超时

public void reorderList(ListNode head) {
        if(head==null||head.next==null||head.next.next==null){    //当结点的个数小于等于2时，不需要做任何操作。
            return ;
        }
        ListNode rearNode=null;                                   //该指针指向链表的尾结点
        ListNode currentNode =head;                              //前面的结点进过了插入
        ListNode preNode=null;                                    //永远指向rearNode结点的前面一个结点
        while(currentNode!=null){                            
            rearNode=currentNode;
            while(rearNode.next!=null){                            //寻找尾结点
                preNode=rearNode;
                rearNode=rearNode.next;
            }
            
            if(rearNode!=currentNode){                      //当rearNode与currentNode结点相等时，表示已经结束
                preNode.next=null;
                rearNode.next=currentNode.next;
                currentNode.next=rearNode;
                currentNode=rearNode.next;
            }
            else{
                break;
            }
        }
    }

2、时间较快的解法，该算法主要分为三个部分：

a、寻找链表的中间结点（midNode），并将链表分一分为二；一个链表的头结点分别为head和newHead；

b、将链表newHead进行反转；

c、将反转后的链表分间隔的插入都head链表中去。

d、时间复杂度为O(n)

代码实现如下：

package com.edu.leetcode;

import com.edu.leetcode.*;

public class ReorderList {

    public void reorderList(ListNode head){
        if(head==null||head.next==null||head.next.next==null){    //当结点的个数小于等于2时，不需要做任何操作。
            return ;
        }
        /*
         * 第一部分主要是用来寻找链表的中间结点
         */
        ListNode midNode=head;                             //寻找链表的中间结点
        ListNode rearNode=head.next;                        //midNode走一步，readNode走两步
        while(rearNode!=null){
            rearNode=rearNode.next;    
            if(rearNode!=null){
                midNode=midNode.next;
                rearNode=rearNode.next;
            }
        }
    /*
     * 第二部是将链表对半分为两个部分，并将后面那个链表进行反转
     */
    
        ListNode newHead=midNode.next;
        midNode.next=null;
        ListNode curentNode=newHead;     //该结点用来指向第一结点，并且永远不需要移动位置
        rearNode=curentNode.next;                //currentNode后面的一个结点
        while(rearNode!=null){                    //将currentNode后面的一个结点放到头结点（newHead）的前面
            curentNode.next=rearNode.next;
            rearNode.next=newHead;
            newHead=rearNode;
            rearNode=curentNode.next;
        }
        
        /*
         * 第三部分将newHead为头结点的链表依次插入到head链表中
         */

        curentNode=head;                     //head中当前插入的位置
        rearNode=newHead;                    //当前的newHead结点
        while(curentNode!=null&&rearNode!=null){   //将rearNode结点插入到curentNode的后面
            newHead=rearNode.next;                              //将newHead重新赋值
            rearNode.next=curentNode.next;
            curentNode.next=rearNode;
            curentNode=rearNode.next;
            rearNode=newHead;
        }
        
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ListNode first1 = new ListNode(0);
        ListNode rear1 =first1;
        
        for(int i=1;i<10;i++){
            ListNode q= new ListNode(i);
            rear1.next=q;
            rear1=q;
        }
        ListNode q=first1;
        while(q!=null){
            System.out.print(q.val+ ",");
            q=q.next;
        }
        System.out.println();
        ReorderList rl = new ReorderList();
        rl.reorderList(first1);
        
        ListNode p=first1;
        while(p!=null){
            System.out.print(p.val+ ",");
            p=p.next;
        }
        System.out.println();
    
    }

}