Cascading boolean expression

Today Leetcode problem is rotating linked list .  Doing it is a no brainer( Answer below). What I suddenly realize is you could pipe the boolean expression to simplify the boolean check later on. To jump straight on:

int k1 = (l == 0 ) ? 0 : k % l;
/* equivalent to 
if(l != 0 )
   k1 = k % l;
else k1 = 0;
*/
if(k1 == 0)
    return head; //rotate with k multiple of list length or list empty

It is like a filter so the end result is just one simple check. I know it won’t make much of a difference but it comes to my mind naturally.

 

Solving the problem

It is just about figuring out where the new Head and new End going to be with the following formula:

newEnd->next = head;  //this is so that oldEnd(the one pointing to NULL) points back to the beginning

newHead = l – k;

newEnd = l -k – 1;

newEnd->next = NULL

l = list length

head = original list head pointer

k = rotation offset

Self explanatory
Rotating list

To find l, we have no other way than loop til the end, then loop to l-k from beginning to find newHead, newEnd.

 

Full code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* rotateRight(ListNode* head, int k) {
        if(k == 0)
            return head;
        ListNode* p = head;
        int l = 0;
        while(p && p->next != NULL){
            p = p->next;
            l++;
        }
        if(p)
            l++;
        int k1 = (l == 0 ) ? 0 : k % l;
        if(k1 == 0)
            return head;
        
        ListNode* newEnd = p;
        if(newEnd)
            newEnd->next = head;
        p = head;
        for(int i = 0; i < l-k1-1; i++, p = p->next){}
        ListNode* newHead = NULL;
        if(p){
            newHead = p->next;
            p->next = NULL;
        }
        return newHead;
    }

Enjoy another chinese song

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s