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}.
------------------------------------------------------------
3 steps:
1) divide list in half
2) reverse the second half
3) merge/reorder
/**
* 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) {
if (head == NULL || head->next == NULL) return head;
ListNode *itr = head;
head = NULL;
while (itr != NULL) {
ListNode *tmp = itr->next;
itr->next = head;
head = itr;
itr = tmp;
}
return head;
}
void reorderList(ListNode *head) {
// find the second half
if (head == NULL || head->next == NULL) return;
ListNode *slow = head, *fast = head;
while (fast != NULL) {
fast = fast->next;
if (fast!= NULL) {
slow = slow->next;
fast = fast->next;
}
}
// reverse
ListNode *head2 = slow->next;
slow->next = NULL;
head2 = reverseList(head2);
// merge
ListNode *cur = head;
while (head2 != NULL) {
ListNode *temp = cur->next;
ListNode *temp2 = head2->next;
cur->next = head2;
cur = temp;
head2->next = cur;
head2 = temp2;
}
}
};
Solution#2, recursive(to do)
Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
------------------------------------------------------------
Similar to #94 Binary Tree Inorder Traversal
using stack, push right node first, then left node
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> ret;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node == NULL) continue;
ret.push_back(node->val);
s.push(node->right);
s.push(node->left);
}
return ret;
}
};
Binary Tree Postorder TraversalGiven a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
----------------------------------------------------
Solution #1, with visited flag
Similar to #94 Binary Tree Inorder Traversal
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> ret;
stack<pair<TreeNode*,bool> > s;
s.push(make_pair(root,false));
while (!s.empty()) {
pair<TreeNode*,bool> p = s.top();
if (p.first != NULL) {
if (p.second == false) {
s.top().second = true;
s.push(make_pair(p.first->right,false));
s.push(make_pair(p.first->left,false));
}else {
ret.push_back(p.first->val);
s.pop();
}
}else {
s.pop();
}
}
return ret;
}
};
Solution #2, without visited flag
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> ret;
if (root == NULL) return ret;
stack<TreeNode*> s;
s.push(root);
TreeNode* pre = NULL;
while (!s.empty()) {
TreeNode* cur = s.top();
// traverse down the tree
if (!pre || pre->left == cur || pre->right == cur) {
if (cur->left != NULL) {
s.push(cur->left);
}else if (cur->right != NULL) {
s.push(cur->right);
}else {
// reach a leaf node
ret.push_back(cur->val);
s.pop();
}
}
else if (cur->left == pre) {
// traverse from the left
if (cur->right != NULL) {
s.push(cur->right);
}else {
ret.push_back(cur->val);
s.pop();
}
}else if (cur->right == pre) {
// from the right
ret.push_back(cur->val);
s.pop();
}
pre = cur;
}
return ret;
}
};
Solution#3, using two stacksFurther reading
http://leetcode.com/2010/10/binary-tree-post-order-traversal.html
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> roots;
stack<TreeNode*> rights;
vector<int> rt;
while (root != NULL || !roots.empty() || !rights.empty()) {
if (root != NULL) {
roots.push(root);
if (root->right != NULL) {
rights.push(root->right);
}
root = root->left;
}else {
if (!rights.empty() && roots.top()->right == rights.top()) {
root = rights.top();
rights.pop();
}else {
rt.push_back(roots.top()->val);
roots.pop();
}
}
}
return rt;
}
};
Update on Feb-1st-2015post-order is left -> right -> root, we can traverse the tree backwards: root -> right -> left, then reverse the result
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> st;
vector<int> rt;
if (root == NULL) return rt;
st.push(root);
while (!st.empty()) {
TreeNode *node = st.top();
st.pop();
rt.push_back(node->val);
if (node->left != NULL) {
st.push(node->left);
}
if (node->right != NULL) {
st.push(node->right);
}
}
reverse(rt.begin(),rt.end());
return rt;
}
};
Insertion Sort List
Sort a linked list using insertion sort.
---------------------------------------------------
wiki
http://en.wikipedia.org/wiki/Insertion_sort
/**
* 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) {
ListNode *dummy = new ListNode(INT_MIN);
dummy->next = head;
ListNode *itr = head, *sorted = dummy;
while (itr != NULL) {
if (itr->val >= sorted->val) {
itr = itr->next;
sorted = sorted->next;
}else {
ListNode *n = dummy;
while (n->next->val <= itr->val) {
n = n->next;
}
ListNode *tmp = itr->next;
ListNode *tmp2 = n->next;
n->next = itr;
itr->next = tmp2;
sorted->next = tmp;
itr = tmp;
}
}
return dummy->next;
}
};
