链表刷题(c语言)_c语言链表刷题

力扣

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* tail = NULL;
    while (cur)
    {
        if (cur->val == val)
        {
            struct ListNode* next = cur->next;
            if (tail == NULL)
            {
                head = next;
            }
            else
            {
                tail->next = cur->next;
            }
            free(cur);
            cur = next;
        }
        else
        {
            tail = cur;
            cur = cur->next;
        }
    }
    return head;
}

链表中倒数第k个结点_牛客题霸_牛客网

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow = pListHead;
        struct ListNode* fast = slow;
        while(k--)
        {
            if(fast)
                fast = fast->next;
            else
                return NULL;
        }
         
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
         
        return slow;
    }

链表分割_牛客题霸_牛客网

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* headless = (ListNode*)malloc(sizeof(ListNode));
        ListNode* headgreater = (ListNode*)malloc(sizeof(ListNode));
        headless->next = headgreater->next = NULL;
        ListNode* curless = headless;
        ListNode* curgreater = headgreater;
        ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                curless->next = cur;
                curless = curless->next;
            }
            else
            {
                curgreater->next = cur;
                curgreater = curgreater->next;
            }
            cur = cur->next;
        }
        curgreater->next = NULL;
        curless->next = headgreater->next;
        pHead = headless->next;
        free(headless);
        free(headgreater);
        return pHead;
    }
};

链表的回文结构_牛客题霸_牛客网

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* slow = A;
        ListNode* fast = A;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* prev = NULL;
        ListNode* cur = slow;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        while(prev)
        {
            if(A->val == prev->val)
            {
                A = A->next;
                prev = prev->next;
            }
            else
            {
                return false;
            }
        }
        return true;
        
    }
};

力扣

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

力扣

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* prev = head;
    struct ListNode* cur = head;
    while(cur && cur->next)
    {
        prev = prev->next;
        cur = cur->next->next;
    }
    return prev;
}

力扣

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    struct ListNode* tail = head;
    struct ListNode* curA = list1;
    struct ListNode* curB = list2;
    while(curA && curB)
    {
        if(curA->val < curB->val)
        {
            tail->next = curA;
            curA = curA->next;
        }
        else
        {
            tail->next = curB;
            curB = curB->next;
        }
        tail = tail->next;
    }
    if(curA == NULL)
    {
        tail->next = curB;
    }
    else
    {
        tail->next = curA;
    }
    struct ListNode* Head = head->next;
    free(head);
    return Head;
 
}