Time Limit Error


#1

my code was partially correct but they …it is showing time limit error…please give a look and help me improving my code

/**

  • Definition for singly-linked list.
  • struct ListNode {
  • int val;
    
  • ListNode *next;
    
  • ListNode(int x) : val(x), next(NULL) {}
    
  • };
    /
    void insert_at_head(ListNode &head,int val)
    {
    ListNode
    n = new ListNode(val);
    n->next = head;
    head = n;
    }
    void insert_at_tail(ListNode &head,int val)
    {
    ListNode
    temp = head;
    if(head == NULL)
    {
    insert_at_head(head,val);
    }
    else
    {
    while(temp->next != NULL)
    {
    temp = temp->next;
    }
    temp->next = new ListNode(val);
    temp->next->next = NULL;
    }
    }
    ListNode
    Solution::partition(ListNode* A, int B) {
    ListNode* less = NULL;
    ListNode* more = NULL;
    //1. we need two split linked list in two parts
    ListNode* temp = A;
    if(A == NULL || A->next == NULL)
    {
    return A;
    }
    while(temp != NULL)
    {
    if(temp->val >= B)
    {
    insert_at_tail(more,temp->val);
    }
    else
    {
    insert_at_tail(less,temp->val);
    }
    temp=temp->next;
    }
    //2. now we need to connect list less with list more
    if(less != NULL)
    {
    A = less;
    ListNode* t = less;
    while(t->next != NULL)
    {
    t = t->next;
    }
    t->next = more;
    return A;
    }
    else
    {
    A = more;
    return A;
    }

}


#2

Hey,
For inserting a new node in the lists ‘more’ and ‘less’, maintain a tail variable for these lists (each) so the function insert_at_tail(ListNode &head, int val) doesn’t traverse the whole list each time there is a new node insertion.
Something like :
ListNode* t = less;
ListNode* t_tail = less;

And call the function on tail:
insert_at_tail(t_tail, val);
where,
void insert_at_tail(ListNode &t_tail, int val)
{

if(t_tail== NULL)
{
insert_at_head(t_tail, val);
}
else
{
t_tail->next = new ListNode(val);
t_tail = t_tail.next;
}
}