Java solution with Stack


  • 0
    T
    public class Solution {
        public void reorderList(ListNode head) {
            if(head == null) return;
            ListNode fast = head;
            ListNode slow = head;
            Stack<ListNode> stack = new Stack<ListNode>();
            while(fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            if(fast != null) {
                slow = slow.next;
            }
            /*Save the latter part of the list in stack*/
            while(slow != null) {
                stack.push(slow);
                slow = slow.next;
            }
            slow = head;
            fast = head;
            /*pop the stack and insert into the fist part of the list*/
            while(fast != null && fast.next != null && !stack.empty()) {
                ListNode top = stack.pop();
                ListNode temp = slow.next;
                fast = fast.next.next;
                slow.next = top;
                top.next = temp;
                slow = temp;
            }
            slow.next = null;
        }
    }

  • 1
    C

    I got the same problem with recursive solution as follow and have no idea about the reason because there is nothing mentioned in the question.

        public void reorderList(ListNode head) {
    		ListNode end = head, begin = head;
    		deepSearch(begin, end);
    	}
    
    	public ListNode deepSearch(ListNode begin, ListNode end) {
    		
    		if (end!=null&&end.next != null) {
    			 begin = deepSearch(begin, end.next);
    		}
    		
    		if(begin == null) return begin;
    		
    		if (begin.next == end || begin == end){
    			end.next = null;
    			return null;
    		}
    		else {
    			end.next = begin.next;
    			begin.next = end;
    			return end.next;
    		}
    	}
    

Log in to reply
 

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