LeetCode Online Judge-2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

//C Program: Add Two Numbers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int val;
    struct ListNode* q = l1;
    struct ListNode* p;
    while (l1&&l2)
    {
        p = l1;
        val = l1->val + l2->val;
        l1->val = val % 10;
        if (val >= 10)
        {
            if (!l1->next)
            {
                l1->next = (struct ListNode*)malloc(sizeof(struct ListNode));
                l1->next->val = 0;
                l1->next->next = NULL;
                if (!l2->next)
                {
                    l2->next = (struct ListNode*)malloc(sizeof(struct ListNode));
                    l2->next->val = 0;
                    l2->next->next = NULL;
                }
            }
            l1->next->val += 1;
        }
        l1 = l1->next;
        l2 = l2->next;
    }
    while (l1&&l1->val>=10)
    {
        l1->val %= 10;
        if (!l1->next)
        {
            l1->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            l1->next->val = 1;
            l1->next->next = NULL;
            break;
        }
        l1->next->val += 1;
        l1 = l1->next;
    }
    if (l2)
    {
        p->next = l2;
    }
    return q;
}

C Program: Isomorphism of Trees

Isomorphism of Trees

Given two trees T1 and T2. If T1 can become the same as T2 through swapping left and right children several times, then we consider these two trees are "isomorphic". For example, Figure 1 shows two isomorphic trees. If we swap the left and right children of nodes A, B, G of either tree, we can get another tree. But in Figure 2, the trees are not isomorphic.

Figure 1

Figure 2

Now given two trees, please determine whether they are isomorphic.

Input Specification:

Enter the information of 2 binary tree. For each tree, give a non-negative integer N($\le 10$) in the first line, which is the number of the tree nodes(the nodes are numbered from 0 to N - 1). Then N lines follewed, the ith line is related to No.i node, giving a capital letter in English stored in this node, the serial number of the left child node, and that of the right child node. If a child node is empty, give a "-" in the corresponding position. Every two given data should be separated with a space. Note: this question make sure that letters stored in all nodes are different from each other.

Output Specification:

If the two trees are isomorphic, print "Yes". Otherwise, print "No".

Sample Input 1 (Figure 1):

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

Sample Output 1:

Yes

Sample Input 2 (Figure 2):

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

Sample Output 2:

No

My program is following.

//Isomorphism of Trees

#include <stdio.h>
#include <stdlib.h>

//Tree node and pointer
typedef struct TreeNode
{
    char data;
    int left;
    int right;
} TreeNode, *Tree;

Tree tree1, tree2;//Two trees
Tree BuildTree(Tree* tree);
int Isomorphic(Tree p1, Tree p2);

int main(void)
{
    Tree T1, T2;
    T1 = BuildTree(&tree1);
    T2 = BuildTree(&tree2);
    if (Isomorphic(T1, T2))
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}

//To build a binary tree
Tree BuildTree(Tree* tree)
{
    int i, N;
    char leftc, rightc;
    scanf("%d", &N);
    getchar();
    *tree = (Tree)malloc(N * sizeof(TreeNode));//Expressing a binary tree through an array of structures
    if (N == 0)
    {
        return NULL;//Empty tree
    }
    int* flag = (int*)malloc(N * sizeof(int));
    for (i = 0; i < N; ++i)
    {
        flag[i] = 1;
    }
    for (i = 0; i < N; ++i)
    {
        scanf("%c %c %c", &((*tree + i)->data), &leftc, &rightc);//Input node information by characters
        getchar();
        if (leftc >= '0'&&leftc <= '9')
        {
            (*tree + i)->left = leftc - '0';//Having left child, transform the character to subscript of left child
            flag[(*tree + i)->left] = 0;
        }
        else
        {
            (*tree + i)->left = -1;//No left child, set it to -1
        }
        if (rightc >= '0'&&rightc <= '9')
        {
            (*tree + i)->right = rightc - '0';//Having right child, transform the character to subscript of right child
            flag[(*tree + i)->right] = 0;
        }
        else
        {
            (*tree + i)->right = -1;//No right child, set it to -1
        }
    }
    for (i = 0; i < N; ++i)
    {
        if (flag[i])
        {
            return *tree + i;
        }
    }
}

//To judge whether two trees are isomorphic
int Isomorphic(Tree p1, Tree p2)
{
    if (p1<tree1&&p2<tree2)//Both p1 and p2 are empty
    {
        return 1;
    }
    if ((p1<tree1&&p2>=tree2)||(p1>=tree1&&p2<tree2))//one of p1 and p2 is empty, another is not empty
    {
        return 0;
    }

    //Both p1 and p2 are not empty
    if (p1->data != p2->data)//Root node elements not equal
    {
        return 0;
    }
    return Isomorphic(tree1 + p1->left, tree2 + p2->left) && Isomorphic(tree1 + p1->right, tree2 + p2->right) || Isomorphic(tree1 + p1->left, tree2 + p2->right) && (Isomorphic(tree1 + p1->right, tree2 + p2->left));
}

C Program: Pop Sequence

Pop Sequence

Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of 1, 2, 3, ..., $N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if $M$M is 5 and $N$N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): $M$ (the maximum capacity of the stack), $N$ (the length of push sequence), and $K$ (the number of pop sequences to be checked). Then $K$ lines follow, each contains a pop sequence of $N$ numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

My C program is following.

//Pop Sequence

#include <stdio.h>
#include <stdlib.h>

int possible(int* s, int M, int N);
int maxlessthantemp(int* t, int temp);

int main(void)
{
	int M, N, K, i, j;
	scanf("%d %d %d", &M, &N, &K);
	int* p = (int*)malloc(K * sizeof(int));//To mark whether every one of these K sequences is a possible pop sequence of the stack

        int* seq = (int*)malloc(N * sizeof(int));//To point to a specific sequence
	for (i = 0; i < K; ++i)
	{
		for (j = 0; j < N; ++j)
		{
			scanf("%d", &seq[j]);
		}
		if (possible(seq,M,N))
		{
			p[i] = 1;//Possible pop sequence. Set p[i] to 1
		}
		else
		{
			p[i] = 0;//Impossible. Set p[i] to 0 

                }
	}
	for (i = 0; i < K; ++i)
	{
		if (p[i])
		{
			printf("YES\n");//Possible to pop. Print "YES"
		}
		else
		{
			printf("NO\n");//Impossible to pop. Print "YES"

 		}
	}
	return 0;
}

//To judge whether a specific sequence is possible to pop
int possible(int* s, int M, int N)
{
	int i;
	if (*s > M)
	{
		return 0;//The first element to pop is *s, which means elements 1~*s have been pushed. If the number of elements in the stack(*s) is more than M, this sequence doesn't match related demand

 	}
	int temp = *s;//To mark the popping element. *s is popped now.
	int* t = (int*)malloc(N * sizeof(int));//To mark which element(s) have/has been popped in this sequence
	for (i = 0; i < N; ++i)
	{
		*(t + i) = i+1;//Not popped yet. Set it to related element value
	}
	*(t-1+*s) = 0;//*s is popped. Set *(t-1+*s) to 0
	for (i = 1; i < N; ++i)
	{
		if (*(s + i) < maxlessthantemp(t,temp))
		{
			return 0;//Not proper popping element. Return 0
		}
		/* In the circumstances of *(s + i) > maxlessthantemp(t, temp) (Only pushing operation may cause overflowing, constant popping can not),
		the number of elements currently having been pushed subtracts the number of those elements who have been popped, gaining the number of elements currently in the stack.

                If it's more than M, this sequence can not be popped rightly
		*/
		if (*(s + i) > maxlessthantemp(t, temp)&& *(s + i) - i > M)
		{
				return 0;
		}
		*(t - 1 + *(s + i)) = 0;//Having been popped. Set it to 0
		temp = *(s + i);//To mark the popping element

 	}
	return 1;
}

/*Proper popping element should meet either one of following two conditions:
1.More than the biggist popped element.
2.Less than the biggist popped element, but in this condition, it should be the maximum of those having not been popped.
So, proper popping element in the function possible(int* s, int N) should be more than temp, or the maximum of those haven't been popped among less-than-temp elements.

I defined a function maxlessthantemp(int* t, int temp) to mark the maximum of those haven't been popped among less-than-temp elements, so proper popping element should be at least this value.
*/
int maxlessthantemp(int* t, int temp)
{
	int i;
	//Through the following loops, element i(also *(t+i-1))becomes the maximum of those haven't been popped among less-than-temp elements. Of course, the circumstance i equals 0 should be explained additionally.

	for (i=temp-1;i>0&&*(t+i-1)==0;--i);
	return i;//When i equals 0, set the value to 0
}