#83 Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
删除单链表中反复元素的节点。要考虑链表是否为空，和下一个节点是否存在的特殊情况
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode *p,*temp;
if (head)
{
p = head;
while (p->next)
{
if (p->val != p->next->val)
p = p->next;
else
{
temp = p->next;
p->next = p->next->next;
free(temp);
}
}
}
return head;
}
#88 Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.
合并两个有序数组---前面#21合并两个有序单链表类似---结果保存在nums1(如果空间足够大)
//0ms
void merge(int* nums1, int m, int* nums2, int n) {
int index = m + n -1, i = m - 1, j = n - 1;
while(j>=0)
{
if(i < 0 || nums1[i] < nums2[j])
nums1[index--] = nums2[j--];
else
nums1[index--] = nums1[i--];
}
}
#100 Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
//0ms
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL || q==NULL)
return p == q;
if(p->val == q->val)
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
else
return false;
}
#101 Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
递归写法
//4ms
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool dfs(struct TreeNode* root1, struct TreeNode *root2)
{
if(root1 == NULL||root2 == NULL)
return root1 == root2;
if(root1->val != root2->val )
return false;
else
return dfs(root1->left,root2->right) && dfs(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root) {
if(!root || (!root->left && !root->right))//空树||仅仅有根结点
return true;
else
return dfs(root->left,root->right);
}
好文阅读
发表评论