LeetCodeRecord

https://leetcode-cn.com/problems/add-two-numbers/

#include<stdio.h>
#include<stdlib.h>
  struct ListNode {
      int val;
     struct ListNode *next;
  };
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int nodeSize = sizeof(struct ListNode);
    struct ListNode* resultHead = (struct ListNode*) malloc(nodeSize);
    resultHead->val = 0;
    resultHead->next = NULL;
    struct ListNode* currentNode = resultHead;

    while (l1 != NULL || l2 != NULL) {
        int temp = l1->val + l2->val + resultHead->val;
        currentNode->next = (struct ListNode*) malloc(nodeSize);
        currentNode = currentNode->next;
        currentNode->val = temp % 10;
        currentNode->next = NULL;
        resultHead->val = temp / 10;
        l1 = l1->next;
        l2 = l2->next;
    }
    struct ListNode* notNullList = l1 == NULL ? (l2 == NULL ? NULL : l2) : l1;
    if (notNullList != NULL) {
        while (notNullList != NULL)
        {
            int temp = notNullList->val + resultHead->val;

            currentNode->next = (struct ListNode*) malloc(nodeSize);
            currentNode = currentNode->next;
            currentNode->val = temp % 10;
            currentNode->next = NULL;
            resultHead->val = temp / 10;
            notNullList = notNullList->next;
        }
    }
    if (resultHead->val != 0) {
        currentNode->next = (struct ListNode*) malloc(nodeSize);
        currentNode = currentNode->next;
        currentNode->next = NULL;
        currentNode->val = resultHead->val;
    }
    return resultHead->next;
}

struct ListNode* addTwoNumbers2(struct ListNode* l1, struct ListNode* l2) {
    int nodeSize = sizeof(struct ListNode);
    struct ListNode* resultHead = (struct ListNode*) malloc(nodeSize);
    resultHead->val = 0;
    resultHead->next = NULL;
    struct ListNode* currentNode = resultHead;

    while (l1 != NULL || l2 != NULL) {
        int x = 0;
        int y = 0;
        if (l1 != NULL) {
            x = l1->val;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            x = l2->val;
            l2 = l2->next;
        }

        int temp = x + y + resultHead->val;
        currentNode->next = (struct ListNode*) malloc(nodeSize);
        currentNode = currentNode->next;
        currentNode->val = temp % 10;
        currentNode->next = NULL;
        resultHead->val = temp / 10;
    }
    if (resultHead->val != 0) {
        currentNode->next = (struct ListNode*) malloc(nodeSize);
        currentNode = currentNode->next;
        currentNode->next = NULL;
        currentNode->val = resultHead->val;
    }
    return resultHead->next;
}

struct ListNode* addTwoNumbers3(struct ListNode* l1, struct ListNode* l2) {
    int nodeSize = sizeof(struct ListNode);
    struct ListNode* resultHead = NULL;
    struct ListNode* currentNode = resultHead;
    int carry = 0;
    while (l1 != NULL || l2 != NULL) {
        int x = 0;
        int y = 0;
        if (l1 != NULL) {
            y = l1->val;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            x = l2->val;
            l2 = l2->next;
        }

        int temp = x + y + carry;
        if (currentNode == NULL) {
            currentNode = (struct ListNode*) malloc(nodeSize);
            resultHead = currentNode;
        }
        else {
            currentNode->next = (struct ListNode*) malloc(nodeSize);
            currentNode = currentNode->next;
        }

        currentNode->val = temp % 10;
        currentNode->next = NULL;
        carry = temp / 10;
    }
    if (carry != 0) {
        currentNode->next = (struct ListNode*) malloc(nodeSize);
        currentNode = currentNode->next;
        currentNode->next = NULL;
        currentNode->val = carry;
    }
    return resultHead;
}

HasCycle:

  struct ListNode {
     int val;
     struct ListNode *next;
  };
 

int hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL ) {
        return 0;
    }
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return 1;
        }
    }
    return 0;
}

https://leetcode-cn.com/problems/sort-list/

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

struct ListNode {
    int val;
    struct ListNode *next;
};
//devide
struct ListNode *listSplit(struct ListNode *head) {
    if ( NULL == head) {
        return head;
    }
    struct ListNode *slow = head, *fast = head;
    while ( NULL != fast)
    {
        fast = fast->next;
        if (fast) {
            fast = fast->next;
        }
        if (NULL == fast) {
            break;
        }
        slow = slow->next;
    }

    struct ListNode *temp = slow;
    slow = slow->next;
    temp->next = NULL;
    return slow;
}
//conquer
struct ListNode *merge(struct ListNode *head1, struct ListNode *head2) {
    if (NULL == head1) return head2;
    if (NULL == head2) return head1;
    struct ListNode head;
    struct ListNode *tail = &head;

    while (head1 && head2)
    {
        if (head1->val < head2->val) {
            tail->next = head1;
            head1 = head1->next;
        }
        else
        {
            tail->next = head2;
            head2 = head2->next;
        } 
        tail = tail->next;
    }
    tail->next = NULL != head1 ? head1 : head2;
    return head.next;
}
// recursion
struct ListNode *mergeSort(struct ListNode *head) {
    if (NULL == head || NULL == head->next) {
        return head;
    }

    struct ListNode *head1 = head, *head2 = listSplit(head);
    head1 = mergeSort(head1);
    head2 = mergeSort(head2);
    return merge(head1, head2);
}

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (NULL == headA || NULL == headB) {
        return NULL;
    }

    struct ListNode *pA = headA, *pB = headB;
    while (pA != pB) {
        pA = NULL == pA ? headB : pA->next;
        pB = NULL == pB ? headA : pB->next;
    }
    return pA;
}

struct ListNode *getIntersection(struct ListNode *head, struct ListNode *current) {
    struct ListNode *fast = head, *slow = current;
    while (fast != slow) {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (NULL == headA || NULL == headB) {
        return NULL;
    }
    //merge two list
    struct ListNode *aListTail = NULL, *pA = headA, *result = NULL;
    while (pA != NULL)
    {
        if (pA->next == NULL) {
            aListTail = pA;
        }
        pA = pA->next;
    }
    aListTail->next = headB;

    struct ListNode *slow = headA, *fast = headA;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            //has cycle, find the node
            result = getIntersection(headA, fast);
            break;
        }
    }
    aListTail->next = NULL;
    return result;
}

https://leetcode-cn.com/problems/reverse-linked-list/

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *currentHead =  head->next;
    head->next = NULL;
    while (currentHead)
    {
        struct ListNode *tmp = currentHead;
        currentHead = currentHead->next;
        tmp->next = head;
        head = tmp;
    }
    return head;
}

struct ListNode* reverseList2(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *newHead = reverseList2(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}