当前位置：首页 > article >正文

【LeetCode】移除链表中等于设定值的元素、反转链表

article 2025/1/15 6:56:38

主页：HABUO🍁主页：HABUO

🌜有时候世界虽然是假的，但并不缺少真心对待我们的人🌛

1. 移除链表中设定值的元素

题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例：

输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

输入：head = [], val = 1 输出：[]

输入：head = [7,7,7,7], val = 7 输出：[]

分析：这是我们所做的第一道有关链表的题，当然了，属于简单题，唯一需要分析的就是，在链表中我们怎么进行迭代？至于删除元素我们在实现链表的时候，就已经实现了无论是头删尾删或者指定位置后删，所以这个题很容易解决，除了一些细节需要注意，具体思想见下图：

所以我们先定义一个cur指针指向我们所要删除的节点，但是我们还要访问上一个节点，这不是双向链表，因此我们还需要创建一个prev指针指向cur的前一个节点，因此如上所示的正常情况的代码如下：

if (cur->val == val)
{
    prev->next = cur->next;
    free(cur);
    cur = prev->next;
}
else
{
    prev = cur;
    cur = cur->next;
}

但会产生一个问题就是如果我们一上来就碰到我们所要删除的节点怎么办？因为此时prev指向的为NULL， prev->next就会对NULL解引用，造成错误，如下图所示，所以我们应该对起始位置加以控制。代码实现如下：

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

2.反转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

输入：head = [1,2] 输出：[2,1]

输入：head = [] 输出：[]

分析：本题我们将通过两个方法去解决，第一个方法是三指针法，为什么要用三个指针？其实也不难想，我们的主要思路不就是从第一个开始，把每个节点中所存储的下一个节点的地址都修改成该节点的上一个节点地址，但是下一个节点我该怎么找到，是不是就是内存泄漏了，因此我们需要拿个伪指针来指向它，同样的道理，我们这两个伪指针往前走一步了，但是改变的节点我们又该如何找到呢？是不是又没办法了，因此还需要一个伪指针，总体思路见下图：

主体代码实现如下：

cur->next = prev;
prev = cur;
cur = next;

这里需要注意，如果题中给的链表为空链表，或者只有一个节点，next是不是很容易就造成了对NULL进行解引用，所以，我们先不让next指向cur的下一个，刚开始让next和cur一同指向head，处理办法见下：

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

到此还有一点我们没有注意到，到链表走到最后的时候我们循环控制条件是cur，也就意味着cur为NULL循环才停止，但此时的next怎么办？我们是不是还要处理一下，所以总体代码见下：

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

方法二：头插法，这种方法的思想是借用我们对单链表实现的时候，对头插接口实现的思想的一个延用，就是建立一个新链表，把老链表进行释放掉，这样的一个思想我们只需要将题中所给的链表从前往后逐一的进行头插即可，主题思路见下图：

头插接口的实现我们在前边的单链表的实现的过程中已经涉及，不再详述，这里需要注意的就是我们释放原链表的时候，可以借用head，没必要再重新建立一个伪指针进行指向，head也是我们的一个形参依然可以用，所以代码实现如下：

struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = cur->val;
temp->next = Newhead;
Newhead = temp;
cur = cur->next;
free(head);
head = cur;

新链表的头指针我们是用Newhead进行维护，每新建立一个节点，到数值移植过去之后，都会将Newhead进行更新，因此最终返回Newhead即可，所以总代码如下：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* Newhead = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = cur->val;
        temp->next = Newhead;
        Newhead = temp;
        cur = cur->next;
        free(head);
        head = cur;
    }
    return Newhead;
}

🍁这世界上有各种各样的人，恰巧我们成为了朋友🍁

🌟这不是缘分，只仅仅是我们本就应该是朋友🌟

查看全文

http://www.kler.cn/a/379616.html