Reorder List leetcode java

题目：

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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}.

题解：

题目要重新按照 L₀→L_n→L₁→L_n-1→L₂→L_n-2→…来排列，看例子1->2->3->4会变成1->4->2->3，拆开来看，是{1，2}和{4，3}的组合，而{4，3}是{3，4}的逆序。这样问题的解法就出来了。

第一步，将链表分为两部分。

第二步，将第二部分链表逆序。

第三步，将链表重新组合。

代码如下：

 1     public void reorderList(ListNode head) {

 2         if(head==null||head.next==null)

 3             return;

 4         

 5         ListNode slow=head, fast=head;

 6         ListNode firsthalf = head;

 7         while(fast.next!=null&&fast.next.next!=null){

 8             slow = slow.next;

 9             fast = fast.next.next;

         }

         

         ListNode secondhalf = slow.next;

         slow.next = null;

         secondhalf = reverseOrder(secondhalf);

  

         while (secondhalf != null) {

             ListNode temp1 = firsthalf.next;

             ListNode temp2 = secondhalf.next;

  

             firsthalf.next = secondhalf;

             secondhalf.next = temp1;        

  

             firsthalf = temp1;

             secondhalf = temp2;

         }

         

     }

     

     public static ListNode reverseOrder(ListNode head) {

  

         if (head == null || head.next == null)

             return head;

  

         ListNode pre = head;

         ListNode curr = head.next;

  

         while (curr != null) {

             ListNode temp = curr.next;

             curr.next = pre;

             pre = curr;

             curr = temp;

         }

  

         // set head node's next

         head.next = null;

  

         return pre;

     }

Reference：//http://www.programcreek.com/2013/12/in-place-reorder-a-singly-linked-list-in-java/

巴特西

Reorder List leetcode java

最新文章

热门文章