[LeetCode] Remove Duplicates from Sorted List I && II

Remove Duplicates from Sorted List I

Problem Statement (link):

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.

Analysis:
Use two pointers, one pointer points to the current node, the other pointer advances if there's duplicates.

The time complexity is O(n), where n is length of the linked list. The space complexity is constant.

Code:

/**
 * 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==NULL || head->next==NULL) return head;

        ListNode *p1=head;
        while (p1->next!=NULL) {
            ListNode *p2=p1->next;
            while (p2 && p1->val==p2->val)
                p2=p2->next;

            if (p1->next==p2) // no dup
                p1=p1->next;
            else
                p1->next=p2;
        }
        return head;
    }
};

Remove Duplicates from Sorted List II

Problem Statement (link):

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:
Once the previous problem is understood, the only difference with this problem is that we need to save previous node.

Code:

/**
 * 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==NULL || head->next==NULL) return head;

        ListNode *prev=new ListNode(INT_MIN);
        prev->next=head;
        head=prev;
        while(prev->next!=NULL) {
            ListNode *curr=prev->next;
            // advance pointer if duplicate
            while(curr->next && curr->val==curr->next->val)
                curr=curr->next;

            if (curr!=prev->next) // re-link prev if duplicate
                prev->next=curr->next;
            else    // advance prev if no duplicate
                prev=prev->next;
        }
        return head->next;
    }
};

[LeetCode] Merge k Sorted List

Problem Statement (link):
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Analysis:
There are three types of solutions:

Suppose the list has k linked list, the longest linked list is with length n.

1) Naive approach:
We compare each of the first k nodes' value, find the node with smallest value, pull that node out and add it to the new list. We repeat this process until all nodes are removed from the original list.

The time complexity is O(k*n*k) = O(n*k^2)

2) Similar idea to Merge sort
We merge every two linked lists in sequence, and repeat this merging until we are left only one linked list.
In run 1, we did k/2 pair merges and left with (k+1)/2 linked lists;
In run 2, we did k/4 pair merges and left with (k+1)/4 linked lists;
...

The time complexity is O(n*k*log k), the log k comes from the fact that we did log k merges in total.

The implementation of this algorithm is below in Sol 1.

3) Use container which auto-sort the incoming data. Three possible options we have are: multiset, heap, priority_queue. I choose to implement using priority_queue for no good reason.

The idea is simple: push each node in into a size k priority queue, each time we pop out the top node - the one with smallest value among all others, and connect it to output list. As we will go through each node once, and each push operation cost log k, the overall time complexity is O(n*k*log k).

Code:
Sol 1: Merge sort

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

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int k=lists.size();
        if (k==0) return NULL;
        return recur(lists, 0, k-1);
    }
    ListNode *recur(vector<ListNode *> &lists, int left, int right) {
        if (left<right) {
            int mid=(left+right)/2;
            return mergeTwoLists(recur(lists, left, mid), recur(lists, mid+1, right));
        }
        else
            return lists[left];
    }
    ListNode *mergeTwoLists(ListNode* head1, ListNode* head2) {
        if (!head1) return head2;
        if (!head2) return head1;

        ListNode *head=new ListNode(INT_MIN);
        ListNode *curr=head;

        while(head1 && head2) {
            if (head1->val<head2->val) {
                curr->next=head1;
                head1=head1->next;
            }
            else {
                curr->next=head2;
                head2=head2->next;
            }
            curr=curr->next;
        }
        if (head1) curr->next=head1;
        else if (head2) curr->next=head2;
        return head->next;
    }
};

Sol 2: Priority queue

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

class Solution {
private:
    struct cmp {
        bool operator() (ListNode *n1, ListNode *n2) {
            return n1->val>n2->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size()==0) return NULL;
        priority_queue<ListNode *, vector<ListNode *>, cmp> heap;

        // add all lists' heads in heap
        for (int i=0; i<lists.size(); i++)
            if (lists[i]) // skill NULL lists
                heap.push(lists[i]);

        // dummy head
        ListNode* head=new ListNode(INT_MAX);
        ListNode* curr=head;

        // pop and push
        while(!heap.empty()) {
            curr->next=heap.top();
            heap.pop();
            curr=curr->next;
            if (curr->next)
                heap.push(curr->next);
        }
        return head->next;
    }
};

Takeaways:
All the three data structures/abstract data type (ADT) are capable of storing items in sorted order. They allow user-defined comparison functions comp as well.

	multiset	heap	priority_queue
Type	Container object (ADT)	A way of organizing items in the range	Container adaptor - the standard underlying container is vector
Implementation	Self-balanced BST		Similar to heap, call make_heap, push_heap, pop_heap to maintain heap properties
Complexity (insert, emplace, erase, find, push, pop etc.)	logarithmic in general, but amortized linear or constant in special cases indicated here	Up to linear in three times the range distance	One push_back call to underlying container, one push_heap call on the range *
Key ops	empty begin, end insert, emplace erase find clear	make_heap push_heap pop_heap sort_heap	emplace empty pop push size top
Relatives	unordered_multiset - implemented using hash tables
Other			Default comparison is less, i.e., greatest value at the top

* push_back: in vector case, time complexity is constant in general. But if reallocation happens, the reallocation can be up to linear on the range of the entire data size.
   push_heap: up to logarithmic time cost.

[LeetCode] Insertion Sort List

Problem Statement (link):
Sort a linked list using insertion sort.
Analysis:
We traverse the linked list, once we find a node has a smaller value than that of its previous node, we start another traversal from the very beginning of the linked list to find the right position for that node to insert in.

Note:
- Once we found an unordered node and re-insert it to the right position, we should not advance the prev pointer. For instance: we have 2->4->1->3, the prev pointer points to node 4, and the tmp pointer points to node 1, i.e., we need to re-insert node 1 to its right position. After re-insertion, the list becomes: 1->2->4->3, the prev pointer still points to node 4, if we advance prev to node 3, we would miss re-insertion of node 3. The bool flag is for this purpose.

Extra link:
A very good review of sorting algorithms is summarized here by Yu.

Code: 

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

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head==NULL) return NULL;
        bool inserted=false;
        ListNode *prev=new ListNode(INT_MIN);
        prev->next=head;
        ListNode *begin=prev;

        while(prev->next->next!=NULL) {
            ListNode *cur=prev->next;
            ListNode* tmp=cur->next;
            if (cur->val>tmp->val) {
                locate(begin, cur, tmp);
                inserted=true;
            }
            else if (prev->next->next!=NULL && inserted==false) {
                prev=prev->next;
                inserted=false;
            }
            else
                prev=prev->next;
        }
        return begin->next;
    }

    // locate and insert target node
    void locate(ListNode* begin, ListNode* prev, ListNode* target) { 
        while(begin->next->val<target->val)
            begin=begin->next;

        // insert
        ListNode* tmp=target->next;
        target->next=begin->next;
        prev->next=tmp;
        begin->next=target;
    }
};

[LeetCode] Reorder List

Problem Statement (link):

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}.

Analysis:
If we are given an array, we simply need to interleave the corresponding nodes with O(1) access time. However, linked list doesn't offer us a constant access time and it's too costly to traverse the list every time to access a node.

If we think about how we construct the reordered list, we notice that we want to traverse from L_n to L_(n/2) reversely for insertion, where all the inserted nodes are from the second half of the list. If we could reverse the second half list, we could access each nodes in linear time.

Thus, we use the following algorithm:
1) Split the list into two halves. We find the middle of the list using two pointers - a slow pointer and a fast pointer. This costs us O(n) time.
2) Reverse the second half of the list. This takes O(n) time using the algorithm below.
3) Traverse the two lists one node each time and link pairs together --> O(n) time.

For step 2), it's easy to see that bubble sort would do the work with time O(n^2). But there is a faster way with O(n) time: From the start, we repeatedly insert the current node to the front until we reach the end, i.e.,

Original list:         a --> b --> c --> d
Insert a to front:   b --> a --> c --> d
Insert c to front:   c --> b --> a --> d
Insert d to front:  d --> c --> b --> a
Done.

The overall algorithm takes O(n) time.

Code:

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

class Solution {
public:
    // time: O(N), space: O(1)
    void reorderList(ListNode *head) {
        if (head==NULL || head->next==NULL) return;
        // split list into two halves
        ListNode* slow=head; ListNode* fast=head;
        while(fast!=NULL && fast->next!=NULL) {
            slow=slow->next;
            fast=fast->next->next;
        }

        // Reverse the 2nd half list, slow is head of the 2nd half
        slow=rev(slow);

        // Add 2nd list interleaved to 1st list
        ListNode* cur=head; // don't move head
        ListNode* tmp1=cur->next; ListNode* tmp2=slow->next;

        while(slow!=NULL) {
            tmp1=cur->next; tmp2=slow->next;
            cur->next=slow;
            slow->next=tmp1;
            slow=tmp2;
            cur=tmp1;
        }
        if (tmp1!=NULL) tmp1->next=NULL;
    }

    ListNode* rev(ListNode *head) {
        if (head->next==NULL) return head;
        ListNode* prev=new ListNode(0);
        prev->next=head;
        head=prev;
        ListNode* cur=prev->next;

        while(cur->next!=NULL) {
            ListNode* tmp= cur->next;
            cur->next=tmp->next;
            tmp->next=prev->next;
            prev->next=tmp;
        }
        return prev->next;
    }
};

[LeetCode] Swap Nodes in Pairs

Problem Statement (link):

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.

Analysis:
The problem requires to swap node pairs, e.g., swap(node1, node2), swap(node3, node4). So the thing you need to be careful with is when the list has odd number of nodes, you need to stop traversing the list if there's only one node left.

Code:

/**
 * 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) {
        if (head==NULL) return NULL;
        ListNode *prev=new ListNode(0); // a pesudo node
        prev->next=head;
        ListNode *newHead=prev;
        ListNode *cur1=head, *cur2=head->next;

        while(cur2!=NULL) {
            cur1=prev->next;
            cur2=cur1->next;
            swap(prev,cur1,cur2);
            if (cur1->next==NULL || cur1->next->next==NULL)
                break;
            prev=prev->next->next;
        }
        return newHead->next;
    }

    void swap(ListNode *prev, ListNode*cur1, ListNode*cur2) {
        ListNode *temp=cur2->next;
        cur2->next=cur1;
        cur1->next=temp;
        prev->next=cur2;
    }
};

[LeetCode] Add Two Numbers

Problem Statement (link):

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis:
This problem is quite straight-forward: we traverse the linked list and add corresponding node's values from two given lists to form a new list.

There are several corner cases to consider:
1) Two lists may have different length: we need to consider the extra nodes from longer list.
2) Carry: we need to remember the carry - 1 or 0 - from previous node(s). If it's end of the list and there's a carry, we need to create a new node with value 1.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (l1==NULL && l2==NULL) return NULL;
        ListNode* h1=l1, *h2=l2;
        // add first node
        ListNode* l3=new ListNode((h1->val+h2->val)%10);
        int carry=(h1->val+h2->val>=10)?1:0;
        h1=h1->next; h2=h2->next;
        ListNode* prev=l3;
        // traverse
        while(h1!=NULL && h2!=NULL) {
            ListNode* tmp=new ListNode((h1->val+h2->val+((carry==1)?1:0))%10);
            carry=(h1->val+h2->val+((carry==1)?1:0)>=10)?1:0;
            prev->next=tmp;
            prev=prev->next;
            h1=h1->next;
            h2=h2->next;
        }
        // If list 1 is longer than list 2
        if (h1!=NULL) {
            while(h1!=NULL) {
                ListNode* tmp=new ListNode((h1->val+((carry==1)?1:0))%10);
                carry=(h1->val+((carry==1)?1:0)>=10)?1:0;
                prev->next=tmp;
                prev=prev->next;
                h1=h1->next;
            }
        }
        // If list 2 is longer than list 1
        if (h2!=NULL) {
            while(h2!=NULL) {
                ListNode* tmp=new ListNode((h2->val+((carry==1)?1:0))%10);
                carry=(h2->val+((carry==1)?1:0)>=10)?1:0;
                prev->next=tmp;
                prev=prev->next;
                h2=h2->next;
            }
        }
        // If there's carry at the last node - create a new node->val=1
        if (h1==NULL && h2==NULL && carry==1) {
            ListNode* tmp=new ListNode(1);
            prev->next=tmp;
        }
        return l3;
    }
};

[LeetCode] Copy List with Random Pointer

Problem Statement (link):

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 naive thought is to create a new linked list as we scan through the given list. As we need to separate adding next pointer and adding random pointer (random pointer may point to node that hasn't been constructed yet), the time complexity is O(n^2), dominates by adding random pointer where we need to scan n nodes - worst case - to add 1 node's random pointer.

The trick is to construct the new list nodes in the original list. Let's say we have the following three node list:

                                                                

Note: this image is from here. Courtesy of Lei Zhang.

This algorithm has three steps:
1) Insert new nodes to the original linked list, configure the next pointer of each node --> O(n)
2) Configure the random pointers of each node --> O(n)
3) Break the list --> O(n)

The overall time complexity of O(n).

Code:

/**
 * 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==NULL) return NULL;
        RandomListNode* cur=head;
        // Insert, link next pointers - O(n)
        while(cur!=NULL) {
            RandomListNode* cur1=new RandomListNode(cur->label);
            cur1->next=cur->next;
            cur->next=cur1;
            cur=cur1->next;
        }

        // Relink the random pointers - O(n)
        cur=head;
        while(cur!=NULL) {
            if (cur->random!=NULL)
                cur->next->random=cur->random->next;
            cur=cur->next->next;
        }

        // Break list - O(n)
        RandomListNode* newHead=head->next;
        cur=head;
        while(cur!=NULL) {
            RandomListNode* cur1=cur->next;
            cur->next=cur1->next;
            if (cur1->next!=NULL)
                cur1->next=cur1->next->next;
            cur=cur->next;
        }
 
        return newHead;
    }
};

[LeetCode] Linked List Cycle I & II

Linked List Cycle I

Problem Statement (link here):

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

Analysis:

A straightforward solution is to store each visited node in a vector as we traverse the linked list, and each time we encounter a new node, we compare the node with existing nodes in vector, if we found a match, it implies the list has a cycle; if we move to a NULL node and no match found, it implies the list doesn't have a cycle. This algorithm requires O(n) space and O(n^2) time complexity - searching and comparing.

The problem statement doesn't allow extra space, we need to find another solution. A classic two-pointer technique would work for this problem.

We define a slow pointer and a fast pointer. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there's a cycle, the two pointer will meet again, mathematically; if there's no cycle, the fast pointer will hit NULL before the slow pointer. This algorithm is O(n) in time complexity, and doesn't use any extra space - except for two pointers - O(1).

Code:

/**
 * 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) {
        if (head==NULL || head->next==NULL) return false;
        ListNode *slow = head;
        ListNode *fast = head->next;
       
        while (fast != NULL){
            if (fast == slow)
                return true;
            else if (fast->next == NULL)
                return false;
            else {
                slow = slow->next;
                fast = fast->next->next;
            }
        }
        return false;
    }
};

Take-aways:
Two pointer technique is useful for detecting cycles in a data structure.

Linked List Cycle II

Problem Statement (link here):

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Analysis:

Let's look at an example below:

                                         a --> b --> c --> d --> e --> f --> g
                                                                             |               |
                                                                             j <--  i <-- h

Imagine if we know the number of nodes in the cycle - 6 in the above example, we could use two pointers to find node e: one pointer  points starts at node a, the other pointer starts at 6 nodes away - node g. A bit math shows that if the two pointers moves at the same pace, they would eventually meet at node e, which is exactly the start of the cycle.

Okay, then how could we find the number of nodes in the cycle? Aha, we could use what we learned from Linked List Cycle I, as the two pointers will meet on some node in the cycle, if we fix that meeting node, and do a traverse, we could count the number of nodes it traversed, which is the number of nodes in the cycle.

Obviously, if there's no cycle, the Linked List Cycle I algorithm will tell us so and we could return the function right away.

As we are doing some simple traverses, the time complexity would be linear: O(n), where n is number of nodes in the list.

Code:

/**
 * 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 (head==NULL || head->next==NULL) return NULL;
        // determine if there's a loop
        int num=1;  // number of nodes in cycle
        bool hasCycle=false;
        ListNode *slow=head;
        ListNode *fast=head->next;

        while(fast!=NULL) {
            if (slow==fast) { hasCycle=true; break;}
            else if (fast->next==NULL) return NULL;
            else {
                slow=slow->next; fast=fast->next->next;
            }
        }
        if (!hasCycle) return NULL;
        // find number of nodes - k - in a loop
        // - fix one ptr in cycle, move the other ptr until meet
        fast=fast->next;
        while(slow!=fast) {
            fast=fast->next;
            num++;
        }
        // two pointers moves in same pace, one starts at head, other starts at k node away
        // when they meet, the node is where cycle begins
        slow=fast=head;
        while(num>0) {
            fast=fast->next;
            num--;
        }

        while(slow!=fast) {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};