class ListNode {
public:
int value;
ListNode* next;
ListNode (int v) {
value(v);
next(NULL);
}
}
Q1: reverse linklist
Reverse a singly-linked list.
analysis: operations on linklist is operations on pointers. On most questions, we have to preserve a next and pre pointers of the linklist. To reverse a linklist, we can use both iterative way and recursive way to solve.
M1: iterative way
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* pre = NULL;
while (cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};M2: recursive way
class Solution {
public:
ListNode* reverse(ListNode* head) {
//base case
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* NodeN = reverse(next);
next->next = cur;
cur->next = NULL;
return NodeN;
}
};
time compelxity: O(n)
space complexity: O(1)
Q2: Reverse Linked List In Pairs
Reverse pairs of elements in a singly-linked list.
analysis:
for any reverse problems of linklist, recursion is the most easiest way to solve. recursion need know the base case and recursive rule. for recursive rule, try to solve one simplest case of the begining part of the linklist and treat the rest part of linklist as subproblem, use recursive function to solve the subproblem.
class Solution {
public:
ListNode* reverseInPairs(ListNode* head) {
// write your solution here
//base case
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* NodeN = reverseInPairs(next->next);//this is the subproblem
next->next = cur;
cur->next = NodeN;
return next;
}
};
time complexity: O(n)
space complexity: O(1)
Q3:middle node of linklist
Find the middle node of a given linked list.
analysis:
In linklist, a simple way to find the middle node is use fast and slow pointers. Initially, these two pointers are at the first node and fast pointer move two steps each iteration and slow pointer move one step each iteration. When the fast pointer reaches the end of the linklist, the middle node is the node which slow pointer point to. Notice the corner case when the fast pointer move two steps.
class Solution {
public:
ListNode* middleNode(ListNode* head) {
// write your solution here
//sanity check
if (head == NULL) return NULL;
ListNode* slow = head;
ListNode* fast = head;
//for the number of listnodes in linklist is odd and even
while (fast->next && fast->next->next) { // fast can't be null
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
time complexity: O(n)
space complexity: O(1)
Other related questions using slow and fast pointer is check if the linklist has circle
Q4:Insert to a sorted linklist
Insert a value in a sorted linked list.
analysis:
insert a value in a sorted linked list. the position of the value could be in the head of the list, the tail of the list or somewhere in the linklist. Since the head of the list may be changed, we can use a dummy node to simplify the corner cases. To find the inserted position, we need to find the node with the value larger than the inserted value. case 1: insert to the head, dummy node is the pre node; case2: insert to the tail, outside the while loop,insert after pre node; case 3: insert into the list, insert between the pre and cur node
class Solution {
public:
ListNode* insert(ListNode* head, int value) {
// write your solution here
//the head of the link list may be changed due to the inserted value, apply dummy node
//sanity check
ListNode* nnode = new ListNode(value);
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur != NULL) {
if (cur->value < value) {
pre = cur;
cur = cur->next;
}else {
break; //find the position
}
}
//insert the node
pre->next = nnode;
nnode->next = cur;
return dummy->next;
}
};
time complexity: O(n)
space complexity: O(1)
Q5:Merge Two Sorted Linked Lists
Merge two sorted lists into one large sorted list.
analysis: Since the head of the new Linklist may be changed, use dummy node to simplify the corner cases. Maintain two node pointers, one is dummy node, the other is tail of the new linklist
class Solution {
public:
ListNode* merge(ListNode* one, ListNode* two) {
// write your solution here
//the head may be changed, use dummy node
//sanity check
if (one == NULL) return two;
if (two == NULL) return one;
ListNode* head = new ListNode(0);
ListNode* cur = head;
while (one && two) {
if (one->value < two->value) {
cur->next = one;
cur = one;
one = one->next;
} else {
cur->next = two;
cur = two;
two = two->next;
}
}
if (one) {
cur->next = one;
}else {
cur->next = two;
}
return head->next;
}
};
time complexity: O(n)
space complexity: O(1)
Q6: Partition Linked list
Given a linked list and a target value T, partition it such that all
nodes less than T are listed before the nodes larger than or equal to
target value T. The original relative order of the nodes in each of the
two partitions should be preserved.
analysis:
the method is the same as merge two sorted linklist.If we need to extract some part of the linklist from the whole linklist, we can use dummy node as the new linklist's head to get the sub linklist. One thing is important to notice, after extract the sub linklist, don't forget to unlink the tail of the sub linklist(tail->next = NULL), otherwise, the new linklist may be unlimited long!!!That's terrible. I always make a mistake due to forgetting to unlink the sub linklist from the original linklist.
class Solution {
public:
ListNode* partition(ListNode* head, int target) {
// write your solution here
//sanity check
if (head == NULL || head->next == NULL) return head;
//find two linklist, smaller and larger
ListNode* smaller = new ListNode(0);
ListNode* larger = new ListNode(0);
ListNode* stail = smaller;
ListNode* ltail = larger;
ListNode* p = head;
while (p) {
if (p->value < target) {
stail->next = p;
stail = p;
p = p->next;
} else {
ltail->next = p;
ltail = p;
p = p->next;
}
}
stail->next = larger->next;
//unlink the last node of larger linklist
ltail->next = NULL;
return smaller->next;
}
};
time complexity: O(n)
space complexity: O(1)
Q7: Reorder linked list
Reorder the given singly-linked list N1 -> N2 -> N3 -> N4 ->
… -> Nn -> null to be N1- > Nn -> N2 -> Nn-1 -> N3
-> Nn-2 -> … -> null
analysis:
Some questions about linked list is the composition of other simple problem. The input and output of this problem can be formed by 3 previous problems. Step1: find the middle node of the linklist Step2: reverse the second half of the linklist Step3: twist merge the first half of the linklist and the second half of the linklist. From this problem, we know that by observing the input and output of the problem, try to find solve the problem by composition of simple problems.
class Solution {
private:
ListNode* reverse(ListNode* head) {
//base case
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* nodeN = reverse(next);
next->next = cur;
cur->next = NULL;
return nodeN;
}
public:
ListNode* reorder(ListNode* head) {
// write your solution here
//sanity check
if (head == NULL || head->next == NULL) return head;
//find the middle node of the linklist
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
//slow is the middle node
ListNode* half = slow->next;
slow->next = NULL;
ListNode* second = reverse(half);
//twist merge second and head
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while(head && second){
cur->next = head;
cur = head;
head = head->next;
cur->next = second;
cur = second;
second = second->next;
}
if (head) cur->next = head;
else if (second) cur->next = second;
return dummy->next;
}
};
time complexity: O(n)
space complexity: O(1)
No comments:
Post a Comment