链表操作.c

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

// 删除连表中的节点
void deleteNode(struct ListNode* node) {
    node->val = node->next->val;
    node->next = node->next->next;
}

// 删除链表的倒数第N个节点
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // 代码的鲁棒性，所以必须添加
    if (head == NULL || n <= 0) {
        return NULL;
    }
    
    struct ListNode* preNode = head;
    struct ListNode* curNode = head;
    
    for (int i = 0; i < n; i++) {
        if (curNode->next) {
            curNode = curNode->next;
        } else {
            return NULL;
        }
    }
    
    if (!curNode->next) {
        return head->next;
    }
    
    while (curNode->next) {
        preNode = preNode->next;
        curNode = curNode->next;
    }
    
    preNode->next = preNode->next->next;
    
    return head;
}

//   反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newHead = NULL;
    while (head) {
        struct ListNode* nextNode = head->next;
        head->next = newHead;
        newHead = head;
        head = nextNode;
    }
    
    return newHead;
}

// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    
    struct ListNode*mergeHead = NULL;
    if (l1->val < l2->val) {
        mergeHead = l1;
        mergeHead->next = mergeTwoLists(l1->next, l2);
    } else {
        mergeHead = l2;
        mergeHead->next = mergeTwoLists(l2->next, l1);
    }
    
    return mergeHead;
}

// 环形链表
bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode *fast, *slow;
    fast = head;
    slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            return true;
        }
    }
    
    return false;
}