Problem Statement

You are 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.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

Problem Link

Reorder List - LeetCode

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        
        if(!head)
            return;
        
        int size = 0;
        
        ListNode *temp = head,*ptemp;
        
        while(temp)
        {
            size++;
            temp = temp->next;
        }
        
        int halfsize = size/2;
        
        temp = head;
        
        while(halfsize--)
        {
            ptemp = temp;
            temp = temp->next;
        }
        
        if(size%2==0)//If LL size is even ,disconnect the two lists
        ptemp->next = NULL;
        
        ListNode *curr = temp,*prev = NULL,*currn = NULL;
        
        while(curr)
        {
            currn = curr->next;
            curr->next = prev;
            prev = curr;
            curr = currn;
        }
        
        ListNode *nhead = prev;//head of second half of LL (more nodes are here is LL size is odd)
        ListNode *ohead = head;//head of first half of the LL
        
        
        while(ohead)
        {
            ListNode *temp1 = ohead->next;
            ListNode *temp2 = nhead->next;
            ohead->next = nhead;
            nhead->next = temp1;
            ohead = temp1;
            nhead = temp2;
        }
        
        
        
        
        
        
        
    }
};