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

//链表节点，链表头结点不存储数据
typedef struct _node{
    int             data;
    struct _node *  next;
} node;

typedef node* pnode;

bool empty(pnode head){
    if(NULL == head || NULL == head->next)
        return true;
    return false;
}

pnode add_element(pnode head, int value){
    if (NULL == head) {
        return head;
    }
    
    pnode node = head;
    while (NULL != node->next && value > node->next->data) {
        node = node->next;
    }
    
    if(NULL != node->next && value == node->next->data){
        return head;
    }
    
    pnode new = malloc(sizeof(node));
    if (NULL == new) {
        return head;
    }
    
    new->next   = node->next;
    node->next  = new;
    new->data   = value;
    
    return head;
}

void clear_list(pnode head){
    pnode t = head->next;
    pnode tmp;
    while (NULL != t) {
        tmp = t->next;
        free(t);
        t   = tmp;
    }
    head->next = NULL;
}

bool has_same_element(pnode aHead, pnode bHead){
    if(empty(aHead))
        return false;
    
    if(empty(bHead))
        return false;
    
    aHead = aHead->next;
    bHead = bHead->next;
    
    while (NULL != aHead && NULL != bHead) {
        while (NULL != aHead && NULL != bHead && aHead->data < bHead->data) {
            aHead = aHead->next;
        }
        
        while (NULL != aHead && NULL != bHead && aHead->data > bHead->data) {
            bHead = bHead->next;
        }
        
        if(NULL != aHead && NULL != bHead && aHead->data == bHead->data){
            return true;
        }
    }
    
    return false;
}

pnode merge(pnode aHead, pnode bHead){
    if(NULL == aHead){
        perror("NULL pointer in merge()");
        exit(1);
    }
    
    if(empty(bHead))
        return aHead;
    
    bHead = bHead->next;
    while (NULL != bHead ) {
        add_element(aHead, bHead->data);
        bHead = bHead->next;
    }
    
    return aHead;
}

pnode combine(pnode aHead, int value){
    pnode tmpList = malloc(sizeof(node));
    tmpList->next = NULL;
    add_element(tmpList, value);
    
    pnode head = aHead->next;
    while (NULL != head) {
        add_element(tmpList, head->data + value);
        head = head->next;
    }
    
    merge(aHead, tmpList);
    free(tmpList);
    return aHead;
}

void print_list(pnode head){
    printf("list at %p ",head);
    head = head->next;
    while (NULL != head) {
        printf("%d ",head->data);
        head = head->next;
    }
    printf("\n");
}

bool has_zero_sum(int* value, int count){
    pnode positive = malloc(sizeof(node));
    pnode negative = malloc(sizeof(node));

    for (int i = 0; i < count; i++) {
        if(0 == value[i]){
            return true;
        }else if(0 < value[i]){
            combine(positive, value[i]);
        }else{
            combine(negative, -value[i]);
        }
        
        print_list(positive);
        print_list(negative);
        
        if (has_same_element(positive, negative)) {
            return true;
        }
    }
        
    return false;
}


int main(int argc, const char * argv[])
{
    int value[]={12,34,23,67,-1,2,3,14,15,67,-9,42,56};
    //int value[]={-90,1,2,3,4,5,6,7,8};
    int count = sizeof(value)/sizeof(value[0]);
    
    if (has_zero_sum(value, count)) {
        printf("True\n");
    }else{
        printf("False\n");
    }
    
    return 0;
}