[LeetCode] Sort List

Link : http://oj.leetcode.com/problems/sort-list/
Sort a linked list in O(n log n) time using constant space complexity.

iterative version of merge sort.
Code is ugly and needs substantial modification.

class Solution {
    public:
    
    ListNode *sortList(ListNode *head) {
        if(!head) return NULL;
        ListNode dummy(0);
        dummy.next = head;
        // get length
        int n=0;
        ListNode* cursor=&dummy;
        ListNode* tmp;
        while(cursor->next) { n++; cursor=cursor->next; }
        
        ListNode* current_first=head;
        ListNode* next_first=NULL;
        
        ListNode* merge_head=NULL;
        ListNode* merge_tail=NULL;
        
        // scan using different step
        for(int step=1; step<n; step*=2)
        {
            // initialization
            cursor = &dummy;
            current_first = dummy.next;
            // for each step, merge two adjacent sub lists
            for(int i=0; i<n; i+=step*2)
            {
                next_first = moveNode(current_first, step*2-1);
                if(next_first) // cut link between different sub list
                {
                    tmp = next_first->next;
                    next_first->next = NULL;
                    next_first = tmp;
                }
                merge(current_first, step, merge_head, merge_tail);
                cursor->next = merge_head; // concatenation
                cursor = merge_tail; // ready for next concatenation
                current_first = next_first; // ready for next merge
            }
        }
        return dummy.next;
    }
    
    ListNode* moveNode(ListNode* p, int step)
    {
        while(step-->0&&p) p=p->next;
        return p;
    }
    
    void merge(ListNode* head, int step, ListNode*& merge_head, ListNode*& merge_tail)
    {
        if(head==NULL) return;
        ListNode dummy(0);
        ListNode* tmp;
        
        ListNode* cursor = &dummy;
        ListNode* l1 = head;
        // get second sub-list
        ListNode* l2 = head;
        // get the node pointing to the head of second sub-list
        l2 = moveNode(l2, step-1);
        if(l2) // cut link between different sub list
        {
            tmp = l2->next;
            l2->next = NULL;
            l2 = tmp;
        }
        
        while(l1||l2)
        {
            if((l1&&!l2)||(l1&&l2&& l1->val <= l2->val))
            {
                tmp = l1->next;
                l1->next=NULL;
                cursor->next = l1;
                
                l1=tmp;
                cursor=cursor->next;
            }
            else
            {
                tmp = l2->next;
                l2->next=NULL;
                cursor->next = l2;
                
                l2=tmp;
                cursor=cursor->next;
            }
        }
        merge_head = dummy.next;
        merge_tail = cursor;
    }
    
};

[LeetCode] Insertion Sort List

Link : Insertion Sort List

Sort a linked list using insertion sort.

Analysis:
Quite straight-forward, create a new linked list header,
a) get a list node in original list,
b) find the place to insert it
c) and insert it

Code says!

[LeetCode] LRU Cache

Link : LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

[LeetCode] Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL