Java solution with 3 steps


  • 120
    W

    This question is a combination of Reverse a linked list I & II. It should be pretty straight forward to do it in 3 steps :)

    public void reorderList(ListNode head) {
                if(head==null||head.next==null) return;
                
                //Find the middle of the list
                ListNode p1=head;
                ListNode p2=head;
                while(p2.next!=null&&p2.next.next!=null){ 
                    p1=p1.next;
                    p2=p2.next.next;
                }
                
                //Reverse the half after middle  1->2->3->4->5->6 to 1->2->3->6->5->4
                ListNode preMiddle=p1;
                ListNode preCurrent=p1.next;
                while(preCurrent.next!=null){
                    ListNode current=preCurrent.next;
                    preCurrent.next=current.next;
                    current.next=preMiddle.next;
                    preMiddle.next=current;
                }
                
                //Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
                p1=head;
                p2=preMiddle.next;
                while(p1!=preMiddle){
                    preMiddle.next=p2.next;
                    p2.next=p1.next;
                    p1.next=p2;
                    p1=p2.next;
                    p2=preMiddle.next;
                }
            }

  • 4
    B
    public class Solution {
        public void reorderList(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while(fast!= null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            if (fast != null){
                slow = slow.next;
                fast.next = null;
            }
            fast = head;
            head = fast;
            slow = reverseList(slow);
            while(slow != null){
                ListNode nextSlow = slow.next;
                slow.next = fast.next;
                fast.next = slow;
                fast = slow.next;
                slow = nextSlow;
            }
        }
        
        public ListNode reverseList(ListNode head){
            ListNode newHead = null;
            while (head != null){
                ListNode next = head.next;
                head.next = newHead;
                newHead = head;
                head = next;
            }
            return newHead;
        }
    }
    

    May I know why my code gives memory limit excess error? Thanks.


  • 0
    D

    This is cool!


  • 0
    W

    Thank you!!!


  • 0
    M

    @BroLegend you are not breaking the link between the first half and the second half of the list.


  • 0
    W

    quite elegant!


  • 6
    W

    Thank you! Woww it is my post last year, thanks to Leetcode, I got my dream job!


  • 0
    J

    quite smart! how about your job:D


  • 1
    W

    Haha, my job is great! There are a lot of smart people here, its mission is make transportation as reliable as running water~~~


  • 3

    same here, just breaking down into methods for clarity (C#)

        public void ReorderList(ListNode head) 
        {
            if (head == null) return;
            ListNode head2 = Split(head);
            head2 = Reverse(head2);
            Merge(head, head2);
        }
        
        public ListNode Split(ListNode head)
        {
            ListNode slow = head;
            ListNode fast = head.next;
            
            while (fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            ListNode head2 = slow.next;
            slow.next = null;
            return head2;
        }
        
        public ListNode Reverse(ListNode head)
        {
            ListNode curr = head;
            ListNode prev = null;
            
            while (curr != null)
            {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            
            return prev;
        }
        
        public ListNode Merge(ListNode head1, ListNode head2)
        {
            ListNode curr1 = head1;
            ListNode curr2 = head2;
            
            while (curr1 != null && curr2 != null)
            {
                ListNode next1 = curr1.next;
                ListNode next2 = curr2.next;
                
                curr1.next = curr2;
                curr2.next = next1;
                
                curr1 = next1;
                curr2 = next2;
            }
            
            return head1;
        }
    

  • 0
    R

    thanks. It's a nice solution.


  • 0

    @wanqing Nice and simple with clear explanation!


  • 0
    S

    @jdrogin Clean bro, clean


  • 3
    1. Find the part2;
    2. reverse part2;
    3. append one by one;
    	public void reorderList(ListNode head) {
    		if(head == null) return;
    
    		ListNode slow = head, fast = head;
    		while(fast.next != null && fast.next.next != null){
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    
    		ListNode part2 = new ListNode(-1);
    		ListNode node = slow.next;
    		slow.next = null;
    		part2.next = node;
    		while(node != null && node.next != null){
    			ListNode next = node.next;
    			node.next = next.next;
    			next.next = part2.next;
    			part2.next = next;
    
    		}
    
    		ListNode node1 = head;
    		ListNode node2 = part2.next;
    		while(node2 != null){
    			ListNode next1 = node1.next;
    			ListNode next2 = node2.next;
    			node1.next = node2;
    			node2.next = next1;
    			node1 = next1;
    			node2 = next2;
    		}
    	}

  • 0

    My CPP code:

    
    void reorderList(ListNode* head) 
    {
    	if (!head || !head->next)
    		return;
    	ListNode **p = &head, **q = &head;
    	while (*q && (*q)->next)
    	{
    		p = &(*p)->next;
    		q = &(*q)->next->next;
    	}
    	for (q = &(*p)->next; *q; swap(*p, *q))
    		swap(*p, (*q)->next);
    	for (q = &head->next; *p != *q; q = &(*q)->next->next)
    	{
    		swap(*p, *q);
    		swap(*p, (*q)->next);
    	}
    }
    
    part of the code is from @StefanPochmann 's answer for Reverse Linked List II.
    
    https://discuss.leetcode.com/topic/45392/6-10-lines-in-c

  • 0
    R

    I use stack to store the ListNode but system return: The Limite Exceeded.
    could you point out what wrong with my code.I would thank you for you help.
    my code:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void reorderList(ListNode head) {
        	if(head==null) return ;
            Stack<ListNode> stack=new Stack();
            ListNode cur=head;
            int length=0;
            while(cur!=null){
            	stack.push(cur);
            	cur=cur.next;
            	length++;
            }
            if(length==2) return;
            cur=head;
            while(cur!=stack.peek()){
            	ListNode tmp=cur.next;
            	cur.next=stack.pop();
            	cur.next.next=tmp;
            	cur=tmp;
            }
        }
    }

  • 0
    G

    @wanqing , do you know why I got Memory Limit Exceeded if replace your third reverse logic(Reverse the half after middle ) to the following function?

    public ListNode merge(ListNode head1, ListNode head2)
        {
            ListNode curr1 = head1;
            ListNode curr2 = head2;
            
            while (curr1 != null && curr2 != null)
            {
                ListNode next1 = curr1.next;
                ListNode next2 = curr2.next;
                
                curr1.next = curr2;
                curr2.next = next1;
                
                curr1 = next1;
                curr2 = next2;
            }
            
            return head1;
        }
    

  • 1

    @BroLegend you can add "fast.next = None" after the while loop"


  • 0

    @BroLegend
    based on his solution, write Python code:

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def reorderList(self, head):
            """
            :type head: ListNode
            :rtype: void Do not return anything, modify head in-place instead.
            """
            if not head or not head.next:
                return
            
            slow, fast = head, head
            
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            
            tmp = slow.next
            slow.next = None
            slow = tmp
            
            slow = self.reverseLinkedList(slow)
            cur = head
            while slow:
                tmp = slow.next
                slow.next = cur.next
                cur.next = slow
                cur = slow.next
                slow = tmp
                
        
        def reverseLinkedList(self, head):
            prev = None
            cur = head
            
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
    

  • 0
    A

    My code is similar to yours.

    public class Solution {
        public void reorderList(ListNode head) {
            ListNode helper = new ListNode(0);
            helper.next = head;
            ListNode fast = helper;
            ListNode slow = helper;
            
            while(fast!=null&&fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            
            ListNode tail = reverse(slow.next);
            slow.next=null;
            merge(head,tail);
            //return helper.next;
        }
        
        private ListNode reverse(ListNode x){
            ListNode start = null;
            while(x!=null){
                ListNode next = x.next;
                x.next = start;
                start = x;
                x = next;
            }
            return start;
        }
        private void merge(ListNode x, ListNode y){
            
            while(y!=null){
                ListNode xn = x.next;
                ListNode yn = y.next;
                x.next = y;
                y.next = xn;
                x=xn;
                y=yn;
            }
        }
    }
    

Log in to reply
 

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