首页 > 代码库 > 【Leetcode】Reorder List JAVA
【Leetcode】Reorder List JAVA
一、题目描述
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(); }}
【Leetcode】Reorder List JAVA
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。