Sort Linked List Already Sorted Using Absolute Values - Leetcode Solution

Problem statement: Given a linked list that is sorted based on the absolute values of its elements, sort the linked list based on the actual values of its elements.

Example: Input: 1 -> -2 -> -3 -> 4 -> -5 -> NULL Output: -5 -> -3 -> -2 -> 1 -> 4 -> NULL

Solution: This problem can be solved by traversing the linked list and rearranging the nodes based on their values. Here are the steps:

1. Traverse the linked list and create two separate linked lists for positive and negative values.
2. Reverse the negative linked list.
3. Merge the positive and negative linked lists in order to obtain the final sorted linked list.

Let's implement the code for the above steps:

/**

• Definition for singly-linked list.

• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• }; / class Solution { public: ListNode sortList(ListNode* head) { if(head == NULL || head->next == NULL) { return head; }

   // Create separate linked lists for positive and negative values
   ListNode *positive = NULL, *negative = NULL;
   ListNode *curr = head;
   while(curr != NULL) {
       ListNode *temp = curr->next;
       if(curr->val >= 0) {
           curr->next = positive;
           positive = curr;
       } else {
           curr->next = negative;
           negative = curr;
       }
       curr = temp;
   }
   
   // Reverse the negative linked list
   ListNode *prev = NULL;
   curr = negative;
   while(curr != NULL) {
       ListNode *temp = curr->next;
       curr->next = prev;
       prev = curr;
       curr = temp;
   }
   negative = prev;
   
   // Merge the positive and negative linked lists
   ListNode *dummy = new ListNode(0);
   prev = dummy;
   while(positive != NULL && negative != NULL) {
       if(positive->val < negative->val) {
           prev->next = positive;
           positive = positive->next;
       } else {
           prev->next = negative;
           negative = negative->next;
       }
       prev = prev->next;
   }
   
   if(positive != NULL) {
       prev->next = positive;
   }
   if(negative != NULL) {
       prev->next = negative;
   }
   
   return dummy->next;
  

  } };

Time Complexity: O(nlogn) where n is the number of nodes in the linked list. Space Complexity: O(1).

Explanation: We have used two pointers 'positive' and 'negative' to create two separate linked lists for positive and negative values. We have reversed the 'negative' linked list using the standard method of iterating through the linked list and setting the next pointer to the previous node. We have then merged the two linked lists by comparing their values and creating a new linked list with the sorted values. Finally, we have returned the head of the sorted linked list.

1