Leetcode Reorder List problem solution

YASH PAL,

In this Leetcode Reorder List problem solution, we have given the head of a singly linked list. The list can be represented as:

L0 → L1 → … → Ln – 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln – 1 → L2 → Ln – 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Leetcode Reorder List problem solution

Problem solution in Python.

class Solution(object):
    def reorderList(self, head):
        q = []
        while head:
            q.append(head)
            head = head.next
        p = dummy = ListNode(0)

        while len(q)>1:
            h = q.pop(0)
            t = q.pop()
            p.next = h
            h.next = t
            p = t
            p.next = None
        
        if q: 
            p.next = q.pop()
            p = p.next
            p.next = None
            
        return dummy.next

Problem solution in Java.

public void reorderList(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode lastHead = null;
        
        if (slow != null) {
            ListNode next = null;
            ListNode prev = null;
            ListNode current = slow.next;
            
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            
            slow.next = null;
            lastHead = prev;
        }
        
        if (lastHead != null) {
            ListNode firstHead = head;
            
            ListNode firstHeadNext = null;
            ListNode lastHeadNext = null;
            
            while (firstHead != null && lastHead != null) {
                firstHeadNext = firstHead.next;
                lastHeadNext = lastHead.next;
                
                firstHead.next = lastHead;
                lastHead.next = firstHeadNext;
                
                firstHead = firstHeadNext;
                lastHead = lastHeadNext;
            }
        }
    }

Problem solution in C++.

class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode* a = reverse(head->next);
        head->next->next=head;
        head->next=NULL;
        return a;
    }
    
    void reorderList(ListNode* head) 
    {
        if(head==NULL)
            return;
        if(head->next==NULL)
            return;
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast!=NULL && fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* rev =reverse(slow->next);
        slow->next=NULL;
        ListNode* temp=head;
        ListNode* t2=NULL;
        while(temp && rev)
        {
            ListNode* t1=temp->next;
            temp->next=rev;
            t2=rev;
            temp=t1;
            rev=rev->next;
            t2->next=t1;
            t2=t2->next;
        }
        if(rev!=NULL)
            t2->next=rev; 
    }
};

Problem solution in C.

struct ListNode* reverseList(struct ListNode *head)
{
    if (head==NULL) return NULL;
    struct ListNode *pLast=head, *pCur=head->next, *pNext=NULL;
    head->next=NULL;

    while (pCur!=NULL)
    {
        pNext = pCur->next;
        pCur->next = pLast;

        pLast = pCur;
        pCur = pNext;
    }
    return pLast;
}
 
void reorderList(struct ListNode* head) 
{
    if (head==NULL) return NULL;
    int i,len;
    struct ListNode *pCur=head;

    for(len=0; pCur; len++, pCur=pCur->next); 

    pCur=head;
    for(i=1; i<(len+1)/2 ; i++, pCur=pCur->next);
    
    struct ListNode *pLeft = head;
    struct ListNode *pRight = pCur->next;
    pCur->next = NULL;
    pRight = reverseList(pRight);

    struct ListNode *pLeftNext, *pRightNext;
    while (pLeft && pRight) {
        pLeftNext = pLeft->next;
        pRightNext = pRight->next;
        
        pLeft->next = pRight;
        pRight->next = pLeftNext;
        
        pLeft = pLeftNext;
        pRight = pRightNext;
    }
    
    return head;
}

coding problems