[LeetCode] Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */


class Solution {
    ListNode *reverse(ListNode *node)
    {
        ListNode *res = NULL;
        while(node)
        {
            ListNode *t = node->next;
            node->next = res;
            res = node;
            node = t;
        }
        return res;
    }
public:
    bool isPalindrome(ListNode* head) {
        if(!head) return true;
        
        ListNode *slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        if(fast) slow = slow->next;

        slow = reverse(slow);
        
        while(slow && head)
        {
            if(slow->val != head->val) return false;
            slow = slow->next;
            head = head->next;
        }
        return true;
    }
};

[LintCode] Rehashing

The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

size=3, capacity=4

[null, 21, 14, null]
       ↓    ↓
       9   null
       ↓
      null

The hash function is:

int hashcode(int key, int capacity) {
    return key % capacity;
}

here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.

rehashing this hash table, double the capacity, you will get:

size=3, capacity=8

index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]

Given the original hash table, return the new hash table after rehashing .

Example

Given [null, 21->9->null, 14->null, null],

return [null, 9->null, null, null, null, 21->null, 14->null, null]

Note

For negative integer in hash table, the position can be calculated as follow:

• C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
• Python: you can directly use -1 % 3, you will get 2 automatically.

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param hashTable: A list of The first node of linked list
     * @return: A list of The first node of linked list which have twice size
     */    
    int getLen(ListNode *n)
    {
        int len = 0;
        while(n)
        {
            n=n->next;
            len++;
        }
        return len;
    }
    vector<ListNode*> rehashing(vector<ListNode*> hashTable) {
        // write your code here
        int nums = 0;
        int len = hashTable.size();
        if(0 == len) return hashTable;
        
        for(auto e:hashTable)
        {
            nums += getLen(e);
        }
        if(nums < len/10) return hashTable;
        
        int cap = 2*len;
        vector<ListNode*> res(cap, NULL);
        
        for(auto e:hashTable)
        {
            if(!e) continue;
            while(e)
            {
                ListNode *p = e->next;
                int index = (e->val%cap + cap)%cap;
                if(res[index] == NULL) res[index] = e;
                else {
                    ListNode *t = res[index];
                    while(t->next) t = t->next;
                    t->next = e;
                }
                e->next = NULL;
                e = p;
            }
        }
        return res;
    }
};

[LintCode] Delete Digits

Given string A representative a positive integer which has Ndigits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example

Given an integer A = "178542", k = 4

return a string "12"

class Solution {
public:
    string DeleteDigits(string A, int k) {
        if(A.length() < k) return A;

        int j = 0;
        while(j < A.length()-1 && k > 0)
        {
            if(A[j]>A[j+1]){
                A.erase(j,1);
                k--;     
                if(j>0)j--;
            }
            else j++;
        }
        A = A.substr(0, A.length()-k);
        int index = A.find_first_not_of("0");
        return A.substr(index);
    }
};

[LeetCode] Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        ListNode *prev = &dummy;
        prev->next = head;
        while(head && head->next)
        {
            ListNode *tmp = head->next->next;
            head->next->next = head;
            prev->next = head->next;
            head->next = tmp;
            prev = head;
            head = tmp;
        }
        return dummy.next;
    }
};

[LeetCode] Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode *prev = &dummy;
        ListNode *nthNode = head;
        while(head)
        {
            if(0 == n)
            {
                prev = nthNode;
                nthNode = nthNode->next;
            }
            else --n;
            head = head->next;
        }
        
        prev->next = nthNode->next;
        delete nthNode;
        return dummy.next;
    }
};

[LeetCode] Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Analysis: Find the k+1 node from the right, and reorganize the list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    int getLen(ListNode* head)
    {
        int len = 0;
        while(head)
        {
            len++;
            head = head->next;
        }
        return len;
    }
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        ListNode *kthNode = head;
        ListNode *p = head;
        k %= getLen(head);
        if(k == 0) return head;
        k++;
        while(p->next)
        {
            if(1 == k)
            {
                kthNode = kthNode->next;
            }
            else k--;
            p = p->next;
        }
        p->next = head;
        ListNode *ret = kthNode->next;
        kthNode->next = NULL;
        return ret;
    }
};

[LeetCode] Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis:

Firstly we need to maintain a pointer for the previous node of the visiting one. If the visiting node is equal to the next one, find the node which is equal to the visiting one but is not equal to its next one. Remove the duplicate nodes.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        ListNode *prev = &dummy;
        prev->next = head;
        while(head)
        {
            ListNode *next = NULL;
            while(head->next && 
                  head->val == head->next->val)
            {
                next = head->next;
                delete head;
                head = next;
            }
            if(next)
            {   
                prev->next= next->next;
                delete head;
                head = next->next;
            }
            else 
            {
                prev = head;
                head = head->next;
            }
        }
        return dummy.next;
    }
};

[LeetCode] Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3

This is the simplest question. But how many people can get it right at a try?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return NULL;
        ListNode *prev = head, *curr = head->next;
        
        while(curr)
        {
            if(curr->val == prev->val)
            {
                prev->next = curr->next;
                delete curr;
            }
            else
            {
                prev = curr;
            }
            curr = curr->next;
        }
        return head;
    }
};

[LeetCod] Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Analysis:
We need to maintain two points -- one for the tail of the nodes which are less than x, the other for the tail of the node which are greater than or equal to x. Loop the list, for any node, it will be following either of the tails.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode dummy(0);
        ListNode *sTail = &dummy, *lTail;
        sTail->next = head;
        ListNode *p = head;
        while(p)
        {
            if(p->val < x)
            {
                if(sTail->next != p)
                {
                    lTail->next = p->next;
                    p->next = sTail->next;
                    sTail->next = p;
                }
                sTail = p;
            }
            else
            {
                lTail = p;
            }
            p = p->next;
        }
        return dummy.next;
    }
};

[LeetCode] Sort List

Sort a linked list in O(n log n) time using constant space complexity
Regardless the space constrains, it can be solved recursively. Similarly with create BST from a sorted list, it can go by in-order. Solving it in iteration will be tedious.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode *merge(ListNode*l1, ListNode *l2)
    {
        ListNode head(0);
        ListNode *p = &head;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if(l2) p->next = l2;
        else p->next = l1;
        
        return head.next;
    }
    ListNode *sortList(ListNode* & head, int start, int end)
    {
        if(start == end)
        {
            ListNode *p = head;
            //Note, move head to next for the next recursive call
            head = head->next;
            p->next = NULL;
            return p;
        }
        int mid = start + (end-start)/2;
        return merge(sortList(head, start, mid),
                    sortList(head, mid+1, end));
    }
    
public:
    ListNode *sortList(ListNode* head)
    {
        if(!head) return head;
        ListNode *p = head;
        int c = 0;
        while(p->next)
        {
            c++;
            p = p->next;
        }
        return sortList(head, 0, c);
    }
};

[LeetCode] Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Analysis:
If we create a balanced BST using a sorted array, it will be much easier, because we access each element of the array very easily. And the tree can be created by pre-order.
Note, with linked list, we can only easily access the element from left to right, which indicates that we might be able to create the tree by in-order. Each time we create a tree node, we move the linked list pointer to the next.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *listToTreeInner(ListNode*& head, int start, int end) 
    {
        if(start > end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftNode = listToTreeInner(head, start, mid-1);
        TreeNode *current = new TreeNode(head->val);
        current->left = leftNode;
        //Note, we move head to the next for the next node
        head = head->next;
        TreeNode *rightNode = listToTreeInner(head, mid+1, end);
        current->right = rightNode;
        return current;
    }

    TreeNode *sortedListToBST(ListNode *head) 
    {
        if(!head) return NULL;
        int last = 0;
        ListNode* p = head;
        while(p->next) {
            last++;
            p = p->next;
        }
        return listToTreeInner(head, 0, last);
    }
};

[LeetCode] Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode *reverse(ListNode *p)
    {
        ListNode *ret = NULL;
        while(p)
        {
            ListNode * t =p->next;
            p->next = ret;
            ret = p;
            p = t;
        }
        return ret;
    }

    void reorderList(ListNode *head) {
        if(!head) return;
        int c = 0;
        ListNode *p = head, *m=head;
        ListNode *prev = head;
        while(p)
        {
            p=p->next;
            c++;
            if(c%2==0)
            {
                prev = m;
                m=m->next;
            }
        }
        if(c<=2) return;
        
        prev->next = NULL;
        ListNode *r = reverse(m);
        p = head;
        ListNode dummy(0);
        ListNode *ret = &dummy;
        c = 0; 
        while(p&&r)
        {
            if(c%2 ==0)
            {
                ret->next = p;
                ret = p;
                p = p->next;
            }
            else
            {
                ret->next = r;
                ret = r;
                r = r->next;
            }
            c++;
        }
        if(p) ret->next = p;
        else ret->next = r;
    }
};

[LeetCode] Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list

Analysis: A simple solution is to have a hashmap to store the relationship between the original and new node. Alternatively, you can create the new nodes in the original list, making the new and old nodes side by side. It will be looks like:

O1->N1->O2->N2...

To assign the random pointers, you can just do this: O1->next->random = O1->random->next

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) 
    {
        if(!head) return NULL;
        RandomListNode *p = head;
        while(p)
        {
            RandomListNode *next = p->next;
            RandomListNode *newNode = new RandomListNode(p->label);
            p->next = newNode;
            newNode->next = next;
            p = next;
        }
        p = head;
        while(p)
        {
            if(p->random)
            {
                p->next->random = p->random->next;
            }
            p = p->next->next;
        }
        RandomListNode dummy(0);
        RandomListNode *ret = &dummy;
        p = head;
        while(p)
        {
            RandomListNode *next = p->next->next;
            ret->next = p->next;
            ret = p->next;
            p->next = next;
            p = next;
        }
        return dummy.next;
    }
};

[LeetCode] Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Analysis:

Take two pointers, one of which moves one time faster than the other. That is, the slower moves at one node per time, the faster at two nodes per time. If there is a cycle, they will meet at some point P. Suppose the slower pointer has moved X nodes when they meet. The faster pointer has moved 2X. Suppose O is the offset between their starting points. 

If we get another pointer to move from head, and simultaneously the slower pointer moves from P. Both of them move one node per time. After around X steps, we hope they can meet at P again.  For P is in a cycle, that means before they meet at P, they already meet at the point where the cycle begins, let's call it B.

Suppose the starting point of the slower pointer is S from the head. The length of the cycle is C.

C = 2X + O - X = X + O;

To meet at P again, the new pointer should move X + S. Obviously:

X + S = X + O => S = O

Simply we can make S = O = 0. You can also try S = 1 which will give you the same answer.

Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if (NULL==head) return NULL;
        ListNode *slow = head,*fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) break;
        }
        if(fast == NULL || fast->next == NULL) 
            return NULL;
        while (slow != head) {
            slow = slow->next;
            head = head->next;
        }
        return head;
    }
};

[LeetCode] Linked List Cycle I

Given a linked list, determine if it has a cycle in it

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        while(fast != NULL && fast->next != NULL && head != NULL)
        {
            fast = fast->next->next;
            head = head->next;
            if(head == fast) return true;
        }
        return false;
    }
};

[LeetCode] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

 

/* Definition for singly-linked list.
 * 
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    int getLen(ListNode *p)
    {
        int len = 0;
        while(p)
        {
            p=p->next;
            len++;
        }
        return len;
    }
public:
    ListNode *getIntersectionNode(ListNode *headA, 
                                  ListNode *headB) 
    {
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        while(lenA>lenB)
        {
            lenA--;
            headA = headA->next;
        }
        while(lenA<lenB)
        {
            lenB--;
            headB = headB->next;
        }
        while(headA != headB)
        {
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
};

[LeetCode] Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reverse(ListNode* prev, ListNode *tail)
    {
        ListNode* head = prev->next;
        ListNode *ret = tail;
        while(head != tail)
        {
            ListNode *p = head->next;
            head->next = ret;
            ret = head;
            head = p;
        }
        prev->next = ret;
    }
    
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode ret(0);
        ret.next = head;
        ListNode *prevHead = &ret;
        ListNode *p = head;
        int i = 0;
        while(p)
        {
            p = p->next;
            i++;
            if(i % k != 0) continue;
            ListNode *t = prevHead->next;
            reverse(prevHead, p);
            prevHead = t;
        }
        return ret.next;
    }
};

[LeetCode] Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode ret(0);
        ret.next = head;
        ListNode *prev = &ret;
        ListNode *mNode, *nNode, *mPrev;
        int i=1;
        while(head)
        {
            if(i == m)
            {
                mPrev = prev; 
                mNode = head;
            }
            if(i>=m && i<=n)
            {
                ListNode *tmp = head->next;
                head->next = nNode;
                nNode = head;
                head = tmp;
            }
            else
            {
                prev = head;
                head = head->next;
            }
            if(i==n)
            {
                mPrev->next = nNode;
                mNode->next = head;
                break;
            }
            i++;
        }
        return ret.next;
    }
};

[LeetCode] Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode n(0);
        n.next = head;
        ListNode *p = &n;
        while(p->next )
        {
            //Note: to handle duplication
            if(p->next->val == val) 
            {
                ListNode *t = p->next;
                p->next = p->next->next;
                delete t;
            }
            else p = p->next;
        }
        
        return n.next;
    }
};

[LeetCode] Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode node(0);
        ListNode *head = &node;
        
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                head->next = l2;
                l2 = l2->next;
            }
            else
            {
                head->next = l1;
                l1 = l1->next;
            }
            head = head->next;
        }
        if(l1) head->next = l1;
        else head->next = l2;
        
        return node.next;
    }
    ListNode* mergeSort(vector<ListNode *> &lists, int start, int end)
    {
        if(end - start == 1) return mergeTwoLists(lists[start], lists[end]);
        if(start == end) return lists[start];
        return mergeTwoLists(mergeSort(lists, start, (start+end)/2), 
                             mergeSort(lists,(start+end)/2 + 1, end));
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) 
    {
        if(0 == lists.size()) return NULL;
        return mergeSort(lists, 0, lists.size()-1);
    }
};