LeetCode Question: Find the Duplicate Number

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Analysis:

Let's take an example where the array is not ordered, the duplicate is repeated more than once. E.g., the array a = [ 2, 7, 4, 5, 1, 6, 4, 3, 8, 4 ].
Since we could use O(1) extra space, the indices of the array becomes more important for us. Given the indices, this problem becomes finding the indices which are targeting the same value. Note that, the indices are from 0 to n, and the values are from 1 to n. We could consider both the indices and values are nodes in one linked list, and the array (or the index-value pair) represents the connections between the nodes. Thus the array can be converted into a linked list.

Given the linked list, it is not hard to notice that, the duplicates value in array now becomes a loop in the linked list. So, to find if there is a loop (and also the circle strat node), we could use slow and fast pointers which we have seen before:

• Loop detection: If the fast pointer catch up the slow pointer at the same node, there must be a loop.
• Find the loop start node: The distance from head node to the loop start node, and the distance from catchup node to the loop start node, are the same.

So, the last question is how to determine the start point of the linked list. We could use the 1st element, since the index of 1st element in array is always 0, and there is no 0 in the value (it starts from 1). So it is impossible that 1st is in the loop.

Code (C++):

class Solution {

public:

int findDuplicate(vector<int>& nums) {

if (nums.size() > 1){

int slow = nums[0];

int fast = nums[nums[0]];

while (slow != fast){

slow = nums[slow];

fast = nums[nums[fast]];

}

fast = 0;

while (fast != slow){

fast = nums[fast];

slow = nums[slow];

}

return slow;

}

return -1;

}s

};

Code (Python):

class Solution(object):

def findDuplicate(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) > 1:

slow = nums[0]

fast = nums[nums[0]]

while slow != fast:

slow = nums[slow]

fast = nums[nums[fast]]

fast = 0

while slow != fast:

slow = nums[slow]

fast = nums[fast]

return slow

return -1

leetcode Question:Delete Node in a Linked List

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Analysis:

To solve this problem, the key point is "overwrite" !

Usually we are thinking "skip" the node we want to delete by:
1 -> 2 -> 3 -> 4 -> Null, delete 3, we have:
1 -> 2--------> 4 -> Null.

However in this problem, the previous node is unknown.
So, what we should do is to overwrite the node  "3" by node "4":
1 -> 2 -> 3 -> 4->Null, delete 3, we have:
1 -> 2 -> 4->Null.

Just pay attention to the case that the node is the last node.

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node->next){
            node->val = node->next->val;
            node->next = node->next->next;
        }else{
            node = NULL;
        }
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        if node.next:
            node.val = node.next.val
            node.next = node.next.next
        else:
            node = None

leetcode Question: Reverse Linked List

Reverse Linked List

Reverse a singly linked list.

Analysis:

Classic problem. There are multiple algorithms to reverse the linked list. Here in this post I just describe the very basics. Some advanced algorithms can be found in other problems in my blog.

To illustrate the process, say we have the linked list:
  1->2->3->4->5->null
head

In order to reverse it, we define a new pointer:
newhead->null

Iterate the original list, each time insert the node to the start of the new linked list:
1. newhead->1->null
2. newhead->2->1->null
...
5 newhead->5->4->3->2->1->null

Then just return newhead->next.

Code(C++):

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

Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        newhead = ListNode(0)
        while head:
            tmp = newhead.next
            newhead.next = head
            head = head.next
            newhead.next.next = tmp
        return newhead.next
        

leetcode Question: Intersection of Two Linked Lists

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.

Analysis:

Consider the case that two list has equal length, the problem became so easy: only two pointers are needed.  Scan from the start of each list, check if the node are the same. Problem solved !

However, just like the example showed in the question, we need to handle the case when the two list are not equal in length.  What to do then?  Let's make them equal !
(1) Get the length of list A, say n_a.
(2) Get the length of list B, say n_b.
These two steps will take O(n) time. (n = n_a + n_b)
(3) Set two pointers. Make the pointer of longer list abs(n_a-n_b) steps forward.
(4) Scan the two list until find the intersection, or to the end of list.
This step will take O(n) time.

Totally, time complexity is O(n), space complexity is O(1).

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int n1 = 0; //length of headA
        int n2 = 0; //length of headB
        ListNode * a1 = headA; 
        ListNode * a2 = headB;
        
        while (a1){
            n1++;
            a1 = a1->next;
        }
        while (a2){
            n2++;
            a2 = a2->next;
        }
        
        a1 = headA;
        a2 = headB;
        
        while (n1>0 && n2>0){
            if (n1>n2){
                n1--;
                a1 = a1->next;
            }
            if (n2>n1){
                n2--;
                a2 = a2->next;
            }
            if (n2 == n1){
                if (a1 == a2){
                    return a1;
                }else{
                    a1 = a1->next;
                    a2 = a2->next;
                    n1--;
                    n2--;
                }
            }
        }
        return NULL;
    }
};

Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        a = headA
        b = headB
        n1 = 0
        n2 = 0
        
        while a is not None:
            a  = a.next
            n1 += 1
        while b is not None:
            b  = b.next
            n2 += 1
            
        a = headA
        b = headB
        
        while n1 > 0 and n2 > 0:
            if n1 > n2:
                a = a.next
                n1 -= 1
            if n2 > n1:
                b = b.next
                n2 -= 1
            if n1 == n2:
                if a == b:
                    return a
                else:
                    a = a.next
                    b = b.next
                    n1 -= 1
                    n2 -= 1
        return None
        

leetcode Question: Sort List

leetcode Question: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Analysis:

From the post "Common Sorting Algorithms", we know that the sorting algorithms which have O(n log n) complexity are merge sort and quick sort. So in this problem, we can use merge sort to handle!

Different from array data, this problem requires good understanding of linked list operations, e.g., split, merge.  Before doing this problem, I suggest you first check out the problem "Merge Two Sorted List" and "Linked List Cycle", and also the merge sort algorithm itself. Then the problem becomes pretty straightforward.

Like the merge sort, we can do recursively:
(1) Split the list (slow fast pointers)
(2) sort the first part (merge sort)
(3) sort the second part (merge sort)
(4) merge the two parts (merge two sorted lists)

See the code below for details. In this code, the pointer to the pointer (reference pointer) is used, note that to get the pointer where "ptrRef" points, we can use "*ptrRef".

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // Merge two sorted list (save as the leetcode Question 54: Merge Two Sorted Lists)
    ListNode* sortedMerge(ListNode* l1, ListNode* l2){
        ListNode* res = new ListNode(0);
        ListNode* current = res;
        while (true){
            if (!l1){
                current->next = l2;
                break;
            }
            if (!l2){
                current->next = l1;
                break;
            }
            if (l1->val < l2->val){
                current->next = l1;
                l1 = l1->next;
            }else{
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        return res->next;
    }

    // Split a list into two parts, using slow/fast pointers
    void split(ListNode* head, ListNode** aRef, ListNode** bRef){
        ListNode* slow;
        ListNode* fast;
        if (head==NULL || head->next==NULL){
            *aRef = head;
            *bRef = NULL;
        }else{
            slow = head;
            fast = head;
            while (fast!=NULL && fast->next!=NULL){
                fast = fast->next->next;
                if (fast==NULL){break;} // this is important
                slow = slow->next;
            }
            *aRef = head;
            *bRef = slow->next;
            slow->next=NULL;
        }
    }

    // MergeSort LinkedList
    void mergeSort(ListNode** headRef){
        ListNode* head = *headRef;
        ListNode* a;
        ListNode* b;
        
        if (head==NULL || head->next==NULL){
            return;
        }
        
        split(head,&a,&b);   //split the list
        
        mergeSort(&a);       //sort the first part
        mergeSort(&b);       //sort the second part    
        
        *headRef = sortedMerge(a,b);    // merge two sorted part
    }

    //main function
    ListNode *sortList(ListNode *head) {
        mergeSort(&head);
        return head;
    }
};

leetcode Question: Reorder List

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

Analysis:

Let's see some examples:

{1,2,3,4,5,6} ---> {1,6,2,5,3,4}
{1,2,3,4,5,6,7} ---> {1,7,2,6,3,5,4}

One straightforward middle step of such reordering is:
{1,2,3,4,5,6}  --> {1,2,3,6,5,4} --> {1,6,2,5,3,4}
{1,2,3,4,5,6,7}---> {1,2,3,4,7,6,5} ---> {1,7,2,6,3,5,4}

By reversing the last part of the linked list, we do not need to worried about the "parent" pointer anymore. The final step is just insert the each element in the last part into the first part (every two element).

So the algorithm implemented below can be summarized as:
Step 1  Find the middle pointer of the linked list (you can use the slow/fast pointers)
Step 2  Reverse the second part of the linked list (from middle->next to the end)
Step 3  Do the reordering. (inset every element in the second part in between the elements in the first part)

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head){return;}
        if (head->next==NULL){return;}
        ListNode *p=head; 
        ListNode *q=head; 
        
        //find the midddle pointer
        while (q->next && q->next->next){
            p=p->next;
            q=q->next->next;
        }
        
        //now p is middle pointer
        //reverse p->next to end
        q = p->next;
        while (q->next){
            ListNode* tmp = p->next;
            p->next = q->next;
            q->next = q->next->next;
            p->next->next = tmp;
        }
        
        //reorder
        q = head;
        while (p!=q && p->next){
            ListNode* tmp = q->next;
            q->next = p->next;
            p->next = p->next->next;
            q->next->next = tmp;
            q=q->next->next;
        }
        return;
    }
};

leetcode Question: Insertion Sort List

Insertion Sort List

Sort a linked list using insertion sort.

Analysis:

The insertion sorting on array can be found in my previous post (here).
The general idea is insert the current element A[i] into the proper position from A[0]...A[i-1], and A[0]...A[i-1] is already sorted.

In this problem, we can use the same idea and linked list provides a more efficient way for insertion.  Details can be found in the code below. Note that after the insertion, the position of P is unchanged but should not provide another p=p->next operation.

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){return NULL;}
        ListNode *p=new ListNode(0);
        p->next = head;
        head = p;
        ListNode *q;
        
        while (p->next!=NULL){
            q = head;
            bool flag = false;
            while (q!=p){
                if (q->next->val>p->next->val){
                    ListNode* tmp1=p->next;
                    p->next =p->next->next;
                    tmp1->next = q->next;
                    q->next = tmp1;
                    flag =true;
                    break;
                }else{
                    q=q->next;    
                }
            }
            if (!flag){
                p=p->next;
            }
        }
        return head->next;
    }
};

leetcode Question: Linked List Cycle II

Linked List Cycle II

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:

This problem can be viewed as two major steps:
    (1) Detect whether the loop exists in the linked list.
    (2) Find the loop start node if loop exists.

The (1) step can be easily solved using the slow&fast pointers (see Linked List Cycle)
How to deal with step (2)?

Firstly let us assume the slow pointer (S) and fast pointer (F) start at the same place in a n node circle. S run t steps while F can run 2t steps, we want to know what is t (where they meet) , then
just solve:  t mod n = 2t mod n,  it is not hard to know that when t = n, they meet, that is the start of the circle.

For our problem, we can consider the time when S enter the loop for the 1st time, which we assume k step from the head. At this time, the F is already in k step ahead in the loop. When will they meet next time?
Still solve the function:    t mod n = (k + 2t) mod n
Finally, we can find out: t = (n-k), S and F will meet, this is k steps before the start of the loop.

So, the Step (2) can be easily solved after Step(1):
Note that here S and F are not slow or fast pointers, but only regular pointers.
1. Set S to the head.
2. S = S -> next, F = F->next
3. output either one of the pointer until they meet.

Here I show some figure for better illustration:
Note that, from step 5, p (slow pointer) firstly enter the loop, it will go (n-k) steps, and meet with fast pointer q. The rest of step is n-(n-k) = k, steps from current meet point, back to the start of the loop.

Code(C++):

/**
 * 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){return NULL;}
        ListNode *p=head;
        ListNode *q=head;
        while (1){
            if (p->next!=NULL){p=p->next;}else{return NULL;}
            if (q->next!=NULL && q->next->next!=NULL){q=q->next->next;}else{return NULL;}
            if (p==q){ //if find the loop, then looking for the loop start
                q=head;
                while (p!=q){
                    p=p->next;
                    q=q->next;
                }
                return p;
            }
        }
    }
};

Code(python):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        p = head
        q = head
        while True:
            if p.next:
                p = p.next
            else:
                return None
            if q.next and q.next.next:
                q = q.next.next
            else:
                return None
            if p == q:
                q = head
                while p!=q:
                    p = p.next
                    q = q.next
                return p
            
            
            
        

leetcode Question: Linked List Cycle

Linked List Cycle

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

Follow up:
Can you solve it without using extra space?

Analysis:

Currently the best way I can figure out is the classic two pointers.
One pointer is slow (1 step a time)
One pointer is fast (2 steps a time)
If there is a cycle, the two pointers will eventually meet (equal).

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) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (!head){return false;}
        ListNode* p=head;
        ListNode* q=head;
        while(q->next && q->next->next){
            p=p->next;
            q=q->next->next;
            if (p==q){return true;}
        }
        return false;
    }
};