leetCode Question: Two Sum II: Input array is sorted

Two Sum II: Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis:

Since the numbers in array are already sorted, the smallest number is the 1st element, while the largest number is the last. The maximum sum we can get is the  A[start] + A[end].

Once we move the “start” pointer, the sum increases and the sum is going to decrease if we move the “end” pointer to the left.

Therefore, we can just move the two pointers and check the sum each time with the target sum, then the result is obtained by only one loop.

Code (C++):

class Solution {

public:

vector<int> twoSum(vector<int>& numbers, int target) {

vector<int> res;

int left = 0;

int right = numbers.size()-1;

while (left < right){

if (numbers[left] + numbers[right] < target){left++;}

else if (numbers[left] + numbers[right] > target){right--;}

else {

res.push_back(left+1);

res.push_back(right+1);

break;

}

}

return res;

}

};

Code (Python):

class Solution(object):

def twoSum(self, numbers, target):

"""

:type numbers: List[int]

:type target: int

:rtype: List[int]

"""

left = 0

right = len(numbers) - 1

while left < right:

if numbers[left] + numbers[right] < target:

left += 1

elif numbers[left] + numbers[right] > target:

right -= 1

else:

return [left+1, right+1]

return []

leetcode Question: Palindrome Linked List

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?

Analysis:

In order to satisfy the O(n) time and O(1) space requirements, we have to consider in-place check/modify the linked list.  Look at the definition of palindrome, it is easily to find out for a palindrome, if we reverse the second half of the list, the first half and second half are identical.

OK, this is where we start to solve the problem. How about the complexity?
1. First we need to find the middle pointer of the list. It is pretty easy if you remember the slow and fast pointers (similar idea was used in previous leetcode question like here).

2. If we can do the reversing in-place, the space we need are only several temporary pointers. If you remember the previous questions (here), you can easily reverse the list.

The basic idea is shown here by an simple example:
Original list: 1->2->3->4->5
We can have a header pointer: head->1->2->3->4->5
Each time, move current pointer to the first place (which is after head pointer).
head->2->1->3->4->5
head->3->2->1->4->5
head->4->3->2->1->5
head->5->4->3->2->1
Done

3. The reversing step is of O(n) time, then checking two halves will only take O(n), so the overall time complexity is O(n).

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    void reverse_list(ListNode** head_ref){
        ListNode* head = *head_ref;
        ListNode* p = head->next;
        while (p && p->next){
            ListNode* tmp = p->next;
            p->next = p->next->next;
            tmp->next = head->next;
            head->next =tmp;
        }
        *head_ref = head;
    }

    bool isPalindrome(ListNode* head) {
        //Get middle pointer: p1
        ListNode* p1 = new ListNode(0);
        p1->next = head;
        ListNode* p2 = p1;
        while(p2 && p2->next){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        //reverse second half list
        reverse_list(&p1);
        
        //check palindrome
        p1 = p1->next;
        p2 = head;
        while (p1){
            if (p1->val != p2->val){
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

Code(Python):

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

class Solution(object):
    
    def reverse(self, head):
        p = head.next
        while p and p.next:
            tmp = p.next
            p.next = p.next.next
            tmp.next = head.next
            head.next = tmp
            
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        #get middle pointer
        p1 = ListNode(0)
        p1.next = head
        p2 = p1
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
        
        # reverse second half of list
        self.reverse(p1)
        
        # check palindrome
        p1 = p1.next
        p2 = head
        while p1:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True
        
        

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: Remove Linked List Elements

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

Analysis:

This is a fundamental pointer manipulation question.
Just be careful with the case that removing 1st element. In the code below, a new pointer is assigned to link to the 1st element.


Code(C++):

/**
 * 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) {
        if (!head) return NULL;
        ListNode *h = new ListNode(0);
        h->next = head;
        head = h;
        while (h->next){
            if (h->next->val == val){
                h->next = h->next->next;
            }else{
                h = h->next;
            }
        }
        return head->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
    # @param {integer} val
    # @return {ListNode}
    def removeElements(self, head, val):
        if not head:
            return None
        h = ListNode(0)
        h.next = head
        head = h
        while h.next:
            if h.next.val == val:
                h.next = h.next.next
            else:
                h = h.next
        return head.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: Copy List with Random Pointer

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:

This problem returns a new linked list, which has the same value and structure of the original one. First we can create a new linked list without considering the Random pointer, which is straight forward:  Scan every node in the original list and create the new list (line 21- 27 in the code below).

But how to keep the random pointer also correct ? If we only point the new random pointer to the original random pointer, which is not a deep copy (since the deletion of nodes in original list will delete the new one as well).  So, how to memorize the relative position of the random node to the current node? Firstly I think to use the length from head node to the random node. For each node, I stored the position of its random node, same position node in the new list is the random node for the node in the new list. This idea can work, but is not efficient. For every node you have to search from the start to the end to find the random, the total complexity is O(n^2). Can we quickly locate the position of the node?  Yes!  Hash map!  A map with the node as key and node as the value can finish the job! We can use the original list node as the key, and the same node in the new list as the value.  Now the map[node_old] = node_new, therefore the node_new->random = map[node_old->random]. In this way, the complexity decreases to 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) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (!head){return NULL;}
        map<RandomListNode*,RandomListNode*> mp; //map <originalNode, newNode>
        mp.clear();
        RandomListNode *res=new RandomListNode(0);
        RandomListNode *p=head;
        RandomListNode *q=res;
        
        while (p){
            RandomListNode *tmp = new RandomListNode(p->label);
            q->next = tmp;
            mp[p]=tmp;
            p=p->next;
            q=q->next;
        }
        p=head;
        q=res->next;
        while (p){
            if (p->random==NULL){
                q->random==NULL;
            }else{
                q->random = mp[p->random];
            }
            p=p->next;
            q=q->next;
        }
        return res->next;
    }
};

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: 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;
    }
};

leetcode Question 86: Reverse Nodes in k-Group

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

Updated 201309:

Analysis:

First consider the atomic operation in this problem: reverse several nodes.
How to reverse? Let's take an example, we have linked list 3->2->1->4->5->6->7
We wan to reverse 4->5->6 to 6->5->4, so we do the following:
(1) 3->2->1->4->5->6->7
               p              q
(2) 3->2->1----->5->6->4->7
               p             q
(3) 3->2->1--------->6->5->4->7
               p             q

The 1st step is to find the locations q and q, where we want to reverse from p->next to q.
Then while p->next != q,  we do:
     (1) move p->next to q->next
     (2) connect p->next to p->next->next
Note that, p and q are fixed.

Now we solve this reverse problem, the final step is to scan the whole list:
When we finished one reverse, put p k steps further, set q=p, then put q k steps further to find the end node for the new reverse, if meet the end, no more reverse needed, return the list.

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!head){return NULL;}
        ListNode* p=new ListNode(0);
        p->next=head;
        head = p;
        ListNode* q=p;
        while (true){
            int i=0;
            while (q && i<k){q=q->next;i++;}
            if (!q){return head->next;}
            else{
                while (p->next!=q){
                    ListNode* d = p->next;
                    ListNode* l = q->next;
                    p->next=p->next->next;
                    q->next=d;
                    d->next=l;
                }
                for(int j=0;j<k;j++){p=p->next;}
                q=p;
                }
        }
        return head->next;
    }
};

Code(Python):

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

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def reverseKGroup(self, head, k):
        p = ListNode(0)
        p.next = head
        head = p
        q = p
        while True:
            i = 0
            while i < k and q != None:
                q = q.next
                i = i + 1
            if q == None:
                return head.next
            while p.next != q:
                tmp1 = p.next
                tmp2 = q.next
                p.next = p.next.next
                q.next = tmp1
                q.next.next = tmp2
                
            for j in xrange(k):
                p = p.next
            q = p
            
        return head.next
            
        

Old Version:

Analysis:

The idea is to scan from the 1st node to the last, if there are k nodes, then swap them, and count again, until get the end.

In order to swap k nodes, we can have
(1) The previous node, to link the previous list.  (pre)
(2) The 1st node to swap.   (st)
(3) The kth node to swap.  (ed)

The idea is to insert the current 1st node behind the end node.
e.g.
1->2->3->4->null, when k=4

(1)2->3->4->1->null
               ed
(2)3->4->2->1->null
         ed
(3)4->3->2->1->null
    ed

After this swap, do not forget link the swapped list to the previous list.


Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* p=head;
        ListNode* pre=new ListNode(0);
        pre->next=p;
        head = pre;
        int c=0;
        ListNode* st;
        ListNode* ed;
        
        while(p!=NULL){
            c++;
            if (c==1){st = p;} //get start node of every k nodes
            if (c==k){
                ed = p;         // get end node of every k nodes
                ListNode *last=ed;  //store the list after the k nodes
                ListNode *nst=st;   //store the next node to be reversed
                while (st!=ed){     // reverse the k nodes
                    last = ed->next;
                    nst = st->next;
                    st->next = last;
                    ed->next = st;
                    st=nst;
                }
                pre->next = st;     //link to the previous list
                for (int i=0;i<k-1;i++){    //get the end of the k nodes
                    p=p->next;    
                }
                c=0;                //reset count = 0 
            }
            if (c==0){pre = p;}     //store the previous list
            p=p->next;              //go next nodes
        }
        return head->next;
    }
};