Java non-recursive solution


  • 0
    X
    public class Solution {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null) {
                return;
            }
            ListNode Middle = findMid(head);
            ListNode reverseHead = reverseList(Middle.next);
            Middle.next = null;
            ListNode head_all = new ListNode(0);
            ListNode remember = head_all;
            while(head!=null&&reverseHead!=null){
                ListNode head_next = head.next;
                ListNode reverse_next = reverseHead.next;
                head_all.next = head;
                head_all = head_all.next;
                head_all.next = reverseHead;
                head_all = head_all.next;
                head = head_next;
                reverseHead = reverse_next;
            }
            if(head!=null){
                head_all.next = head;
                head_all = head_all.next;
            }
            head = remember.next; 
         
        }
        public ListNode findMid(ListNode head){
            ListNode slow = head;
            ListNode fast = head.next;
            while(fast!=null&&fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
        
        public ListNode reverseList(ListNode head){
            ListNode dummy = null;
            while(head!=null){
                ListNode next = head.next;
                head.next = dummy;
                dummy = head;
                head = next;
            }
            
            return dummy;
        }
    }

Log in to reply
 

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