Find the middle,reverse the last half, insert the last half into the previous half


  • 2
    W
    public class Solution {
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
    	for(;fast!=null&&fast.next!=null;fast=fast.next.next,slow=slow.next);
    	ListNode node = slow;//slow is the middle node
    	ListNode prev = null;
    	while(node!=null){//reverse the nodes of the last half of this linkedlist
    		ListNode temp = node.next;
    		node.next = prev;
    		prev = node;
    		node = temp;
    	}
    	fast = head;
    	while(fast!=slow){//traverse from the head and the middle respectively, insert the last half nodes into the previous half.
    		ListNode temp = fast.next;
    		fast.next = prev;
    		fast = temp;
    		if(fast==prev) break;
    		temp = prev.next;
    		prev.next = fast;
    		prev = temp;
    	}
    }
    

    }


Log in to reply
 

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