Clear and Simple JAVA O(n) solution with O(1) extra space


  • 4
    W
    public class Solution {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null) return;
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode n2 = reverse(slow.next);
            slow.next = null;
            combine(head, n2);
        }
        private ListNode reverse(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode preHead = new ListNode(0);
            ListNode runner = head;
            while (runner != null) {
                ListNode tmp = preHead.next;
                preHead.next = runner;
                runner = runner.next;
                preHead.next.next = tmp;
            }
            return preHead.next;
        }
        private void combine(ListNode n1, ListNode n2) {
            if (n1 == null || n2 == null) return;
            ListNode preHead = new ListNode(0);
            ListNode runner = preHead;
            while (n1 != null && n2 != null) {
                runner.next = n1;
                n1 = n1.next;
                runner.next.next = n2;
                n2 = n2.next;
                runner = runner.next.next;
            }
            runner.next = n1 == null ? n2 : n1;
        }
    }

  • 0
    B
    class Solution {
    

    public:
    void reorderList(ListNode* head)
    {
    if(head == NULL)return;
    int num = 0;
    ListNode* p = head;
    while(p != NULL)
    {
    p = p->next;
    num++;
    }
    p = head;

    	for(int i = 0; i < num/2; i++)
    	    p = p->next;
    	ListNode* prev = p;
    	ListNode* cur = p->next;
    	while(cur != NULL)
    	{
    		ListNode* tmp = cur->next;
    		cur->next = prev;
    		prev = cur;
    		cur = tmp;
    	}
    	p = head;
    	int isleft = true;
    	while(true)
    	{
    		if(head != prev&&isleft)
    		{
    		    ListNode* tmp = head->next;
    			head->next = prev;
    			head = tmp;
    		}
    		else if(head != prev)
    		{
    		    ListNode* tmp = prev->next
    			prev->next = head;
    			prev = tmp;
    		}
    		else 
    		{
    			head->next = NULL;
    			break;
    		}
    		isleft = !isleft;
    	}
    }
    

    };enter code here


Log in to reply
 

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