Java solution with stack


  • 6
    W

    I see no one use stack with java as the same idea as me, so I share my code here.

    It is a bit straightforward, so need not explaination.

    public class Solution {
        public void reorderList(ListNode head) {
            if (head==null||head.next==null) return;
            Deque<ListNode> stack = new ArrayDeque<ListNode>();
            ListNode ptr=head;
            while (ptr!=null) {
                stack.push(ptr); ptr=ptr.next;
            }
            int cnt=(stack.size()-1)/2;
            ptr=head;
            while (cnt-->0) {
                ListNode top = stack.pop();
                ListNode tmp = ptr.next;
                ptr.next=top;
                top.next=tmp;
                ptr=tmp;
            }
            stack.pop().next=null;
        }
    }

  • 0
    P

    I think that the idea is to find a solution without using any other data structures.


  • 0
    Y

    Very smart solution. But it uses extra O(n) space.
    The requirement is in-place.


Log in to reply
 

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