LeetCode算法实战：链表元素剔除与反转操作

LeetCode 算法实践：链表元素移除与反转操作

第一题 - 移除链表元素

方法一 - 原地删除

思路阐述：要实现链表中指定值元素的删除，需分情况处理。一是头节点的值恰好为目标值，此时直接删除头节点并更新头指针；二是中间或尾部节点的值为目标值，需借助前驱节点来完成删除操作。

解题步骤：
- 删除头部目标节点：通过循环判断头节点是否存在且值是否等于目标值。若满足条件，先临时保存头节点，将头节点更新为下一个节点，再释放临时保存的头节点。
- 删除中间和尾部目标节点：初始化临时指针temp指向新的头节点，遍历链表时确保当前节点及其下一个节点非空。若下一个节点的值等于目标值，临时保存该节点，将当前节点的next指针指向其下下个节点，然后释放临时保存的节点；若下一个节点的值不等于目标值，将temp指针后移。
- 返回新头节点：遍历结束后，返回更新后的头节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    while (head != NULL && head->val == val) 
    {
        struct ListNode* tmp = head;
        head = head->next;
        free(tmp);
    }
    struct ListNode* temp = head;
    while (temp != NULL && temp->next != NULL)
     {
        if (temp->next->val == val)
        {
            struct ListNode* cur = temp->next;
            temp->next = cur->next;
            free(cur);
        } 
        else 
        {
            temp = temp->next;
        }
    }
    return head;
}

复杂度分析
- 时间复杂度：O(n)，需遍历链表的每个节点一次。
- 空间复杂度：O(1)，仅使用常数级额外空间存储指针变量。

方法二 - 双指针

思路剖析：利用双指针prev和cur遍历链表，当遇到值为目标值的节点时，调整指针跳过该节点并释放内存。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while (cur != NULL) 
    {
        if (cur->val != val) 
        {
            prev = cur;
            cur = cur->next;
        } 
        else 
        {
            if (cur == head && cur->val == val) 
            {
                head = cur->next;
                free(cur);
                cur = head;
            } 
            else 
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
    }
    return head;
}

代码分析
- 初始化双指针：prev初始化为NULL，用于记录当前节点的前一个节点；cur初始化为头节点head，用于遍历链表。
- 遍历链表：通过while循环遍历链表，直到所有节点处理完毕。
- 处理当前节点：若当前节点值不等于目标值，更新prev并后移cur；若当前节点值等于目标值，根据是否为头节点分别处理，调整指针并释放内存。
- 返回头指针：遍历结束后，返回更新后的头指针。

方法三 - 尾插

思路讲解：遍历原链表，将不等于目标值的节点依次尾插到新链表中，最后返回新链表的头指针。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;
    while (cur) 
    {
        if (cur->val != val) 
        {
            // 尾插
            if (tail == NULL) 
            {
                newhead = tail = cur;
            } 
            else 
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        } 
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if(tail)
    {
        tail->next=NULL;
    }
    return newhead;
}

代码分析
- 初始化变量：cur用于遍历原链表，初始化为原链表头head；newhead为新链表头指针，初始化为NULL；tail为新链表尾指针，初始化为NULL，用于高效尾插节点。
- 遍历原链表：通过while循环遍历原链表，处理每个节点。
- 处理当前节点：若当前节点值不等于目标值，根据新链表是否为空进行尾插操作；若当前节点值等于目标值，释放该节点并继续遍历。
- 处理尾节点指针：遍历结束后，确保新链表尾节点的next指针为NULL。
- 返回新链表头指针：返回新链表的头指针。

第二题 - 反转链表

描述：给定单链表的头节点head，将链表反转并返回反转后的链表。

方法一 - 迭代

思路解析：使用三个指针协同工作，逐步将每个节点的next指针指向前驱节点，实现链表反转。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* tmp = head;
    while(tmp!=NULL)
    {
        tmp = n2->next;
        n2->next=n1;
        n1=n2;
        n2=tmp;
    }
    return n1;
}

代码分析
- 初始化指针：n1初始化为NULL，指向当前处理节点的前驱节点；n2初始化为头节点head，指向当前正在处理的节点；tmp初始化为头节点head，作为临时指针保存后续节点。
- 遍历链表：通过while循环确保遍历完整链表。
- 反转操作：保存后继节点，调整当前节点的next指针指向前驱节点，然后移动指针继续处理。
- 返回新头节点：循环结束后，n1指向原链表最后一个节点，即反转后的新头节点，返回n1。

方法二 - 采用头插创建新链表

思路剖析：遍历原链表，为每个节点创建副本，将副本节点依次插入新链表头部，形成原链表的逆序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL; //新链表的头指针
    while (cur) 
    {
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        if (newNode == NULL) 
        {
            perror("malloc failed");
            // 释放已分配的节点
            while (newHead) 
            {
                struct ListNode* temp = newHead;
                newHead = newHead->next;
                free(temp);
            }
            return NULL;
        }
        newNode->val = cur->val;
        newNode->next = newHead; //头插法：新节点指向当前头
        newHead = newNode;       //更新头指针
        cur = cur->next;
    }
    return newHead; //返回新链表的头结点
}

代码分析
- 初始化变量：cur指向原链表当前节点，初始化为head；newHead为新链表头指针，初始化为NULL。
- 遍历原链表：通过while循环遍历原链表，为每个节点创建副本。
- 头插操作：将副本节点插入新链表头部，更新新链表头指针。
- 错误处理：若内存分配失败，释放已创建的新链表节点并返回NULL。
- 返回结果：遍历结束后，返回新链表的头指针。

总结

至此，对链表相关操作的探索暂告一段落，但编程之路才刚刚起步。编写代码是与计算机逻辑深度交互的过程，虽会在结构设计和算法实现中遇到挑战，但这些经历能加深对代码逻辑和数据组织的理解。愿你在编程之路上持续探索，书写属于自己的精彩篇章，期待下次与你在代码世界中再度相逢，见证你的成长与进步。