Let’s continue…

**Problem Statement**:

**Remove Nth Node from End of List
**

Given a linked list, remove the *n*-th node from the end of list and return its head.

**Example:**

Given linked list:1->2->3->4->5, and. After removing the second node from the end, the linked list becomesn= 21->2->3->5.

**Note:**

Given *n* will always be valid.

**Follow up:**

Could you do this in one pass?

**Solution One: Brute Force
**

The most straightforward way to solve this problem is iterate the whole list once, and we can calculate the length of the list. Then we can simply calculate the index of the node we want to remove. Then we can iterate again to remove it. This is a two-pass solution (It’s not good enough according to the requirement of the problem).

/** | |

* 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) { | |

int len = 0; | |

ListNode* h = head; | |

while(head){ | |

len++; | |

head = head->next; | |

} | |

if(len == 1){ | |

return h->next; | |

} | |

head = h; | |

int index = len – n; | |

if(index == 0) return head->next; | |

for(int i = 0; i< index – 1; i++){ | |

head = head->next; | |

} | |

ListNode *temp = head->next; | |

head->next = head->next->next; | |

delete temp; | |

return h; | |

} | |

}; |

Time Complexity: O(2*L – n) L is the length of the list.

Space Complexity: O(1)

**Solution Two: Two Pointers
**

We can do it in one pass by allocating two pointers, basically, first pointer will move forward n steps before second pointer moves. Then when the first pointer is ready, we iterate both pointers forward until the first pointer reaches the end. Then we can safely delete the nth node.

The only thing we need to care about is the boundary. However, it is not hard. Try to draw all the nodes on paper will help.

/** | |

* 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) { | |

//Handle situation that list is null or only contain one element | |

if(!head || !(head->next)) | |

return nullptr; | |

ListNode *fast = head, *slow =head; | |

int count = 0; | |

while(fast->next != nullptr) | |

{ | |

fast = fast->next; | |

count ++; | |

if(count> n) | |

{ | |

slow = slow->next; | |

} | |

} | |

//Handles situation that we need to delete first node. e.g. [1,2] 2 | |

if(count + 1 == n) | |

{ | |

head = head-> next; | |

delete slow; | |

return head; | |

} | |

ListNode *temp = slow->next; | |

if(temp == nullptr) | |

return nullptr; | |

slow->next = temp->next; | |

delete temp; | |

return head; | |

} | |

}; |

Time Complexity: O(L)

Space Complexity: O(1)

**Problem Statement**:

**Generate Parentheses
**

Given *n* pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given *n* = 3, a solution set is:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

**Solution One: Back Tracing
**

OK, Let’s look at several situations. If the number of left parenthesis is greater than n, then the formation will always be invalid. Another thing is when the number of right parenthesis is greater than the number of left parenthesis, the formation is always invalid as well.

Based on these two assumptions, we can use recursive function to do our job, first we need to set our base ground, when the string size equals to 2*n, which means our valid parentheses meets our goal, we append the temp string with ‘)’, and push the temp to our final result.

Then we recursively call the generate parentheses function. We specifically define the left part and right part. When the number of left parenthesis is less than n, we add left parenthesis; when the number of right parenthesis is less than left parenthesis, we add right parenthesis.

In order to better understanding the recursive call, you need to draw a call tree, with each function call you can draw a node. For example, if n = 2, a tree looks like below:As you can see from the graph, when n = 2, we have two possible solutions: (()) and ()(). The red mark means the condition does not meet, we will not do recursive call here. Each layer means the depth of the recursive function call. If you are struggling with recursion, you should try to draw a tree like this. This will help you understand the general structure of recursive function.

Time Complexity: O(2^(2*n)) We can see from the tree, the height of the tree is 2*n, and potentially we will have maximum 2^(2*n) nodes.

Space Complexity: O(n) The auxiliary space for this recursive function call is at maximum 2*n.

vector<string>res; | |

class Solution { | |

public: | |

void choose(string prix,int left,int right,int times,int num){ | |

if(times==num){ | |

string temp =prix+")"; | |

res.push_back(temp); | |

return; | |

} | |

if(left<num/2){ | |

string temp =prix+"("; | |

choose(temp,left+1,right,times+1,num); | |

} | |

if(right<left){ | |

string temp =prix+")"; | |

choose(temp,left,right+1,times+1,num); | |

} | |

} | |

vector<string> generateParenthesis(int n) { | |

int num =n*2; | |

int left =0,right=0; | |

res.clear(); | |

if(n==0) return res; | |

int times =0; | |

string prix =""; | |

choose(prix,left,right,times+1,num); | |

return res; | |

} | |

}; |

**Solution Two: Permutation
**

Let’s look at this problem from another perspective.

We know that all the valid parentheses should start with “(” first and end with “)”. We can also clear say that we have an index c in between, when we first reach an index c, the number of left parentheses and the right parentheses are both equal. Since the parentheses sequence is valid, which means the parentheses [1 : c-1] and parentheses [c+1: 2*n – 1] should both be valid. Look at the picture below:

We can say each valid parentheses sequence will exist a constant number c, which can divide the parentheses sequence into two parts. For a specific sequence, the c is determined. So, if we want to know all the possible valid permutations of n pairs of parentheses, we only need to know the valid permutations of a pairs parentheses (left part) and n-a-1 pairs parentheses (right part) and combine them with one extra pair of parentheses:

“(” + left + “)” + right

For example, if n = 3, we have several situations:

- left = 0; right = 2; At this time, c = 1 (determined)

The sequence should look like: ()()() or ()(()).

- left = 1; right = 1; At this time, c = 3 (determined)

The sequence should look like: (())(). Only one possible solution.

- left = 2; right = 0; At this time, c = 5 (determined)

The sequence should look like: (()()) or ((())). Similar to situation left = 0, right = 2.

So based on this idea, we create a loop, and iterate c. You can see that c = left * 2 + 1 (1<=c<=2*n-1). This makes sense, because left should be valid parentheses in this case, which means it should be even number. And index start from 0, so c should be odd number.

Time Complexity: Unknown

Space Complexity: Unknown

Let’s see the code, the code is pretty concise:

class Solution { | |

public: | |

vector<string> generateParenthesis(int n) { | |

vector<string> res; | |

if(n == 0) | |

res.push_back(""); | |

else{ | |

for(int left = 0; left < n; left++){ | |

vector<string> tempL = generateParenthesis(left); | |

for(int i = 0; i< tempL.size(); i++){ | |

string l = tempL[i]; | |

vector<string> tempR = generateParenthesis(n – left –1); | |

for(int j = 0; j < tempR.size(); j++){ | |

string r = tempR[j]; | |

res.push_back("(" + l + ")" + r); | |

} | |

} | |

} | |

} | |

return res; | |

} | |

}; |

That’s all for today. Thanks for reading…