My solution in Java.


  • 0
    A

    1.Get the length of the list

    2.According to step 1,the given list could regard as two parts.

    3.Reverse the second half of the list.

    4.Merge two parts of list together.

    public class Solution {
        public int getListLength(ListNode head)
        {
            int length=0;
            ListNode cur=head;
            ListNode nxt=null;
            while(cur!=null)
            {
                nxt=cur.next;
                cur=nxt;
                length++;
            }
            return length;
        }
        public ListNode reverseList(ListNode head,int halfLength)
        {
            int flag=2;
            ListNode pre=head;
            ListNode cur=head.next;
            ListNode nxt=null;
            while(flag<=halfLength)
            {
                flag++;
                nxt=cur.next;
                pre=cur;
                cur=nxt;
            }
            pre.next=null;
            pre=cur;
            cur=cur.next;
            pre.next=null;
            while(cur!=null)
            {
                nxt=cur.next;
                cur.next=pre;
                pre=cur;
                cur=nxt;
            }
            return pre;
        }
        public void reOrder(ListNode head,ListNode last)
        {
            ListNode curHead=head;
            ListNode nxtHead=null;
            ListNode curLast=last;
            ListNode nxtLast=null;
            while(curLast!=null)
            {
                nxtHead=curHead.next;
                nxtLast=curLast.next;
                curHead.next=curLast;
                curLast.next=nxtHead;
                curHead=nxtHead;
                curLast=nxtLast;
            }
        }
        
        public void reorderList(ListNode head)
        {
            int length=getListLength(head);
            if(length<=2) return;
            int halfLength=length%2==0?length/2:(length/2+1);
            ListNode lastNode=reverseList(head,halfLength);
            reOrder(head,lastNode);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.