博客

一.移除链表元素

原题传送门：

力扣

题目：

1.1不带哨兵位的写法

这里我们的大概思路是用到链表中尾插的一种方法，先定义三个指针：



首先看cur->val是否和val相等，如果不相等，就拿下来：



像这样，但是这一步是怎么实现的呢？其实这里就相当于让newhead,tail指向链表的第一个元素

tail = newhead = cur;

像这样：



这就相当于把第一个节点给拿下来了，因为我们先不看第一个节点后面的内容，就是现在我们抽象一点。

好了，现在我们既然把第一个拿下来了，我们接下来要拿第二个：

首先cur指向的位置应该移到下一个元素上面：

cur = cur->next;

然后判断是否是val,不是就移下来：

这一步就是将tail->next = cur,然后tail = tail->next，cur = cur->next。两个指针都指向了下一个元素：



如果此时cur->val == val的话，cur就把这块空间释放掉，然后指向下一个元素。



就这样一步一步的走，肯定要放在循环里面，但是循环什么时候结束呢？

我们发现最后一步其实是这样的，也就是cur遍历结束指向了最后的空指针就停止。

循环结束就真的结束了吗？当然不是我们仔细看上面图：发现5那个元素本来指向的是6,但是现在我们把6去掉了，会不会就造成了5这个节点里的指针变成了一个野指针，所以我们在循环结束后手动置成空：

tail->next = NULL;

大概的流程就是这样了，但是我们还要判断一个特殊情况：

如果给你的链表里的元素全是val，这时候就不会有元素移动下来，因为tail,newhead两个指针刚开始指向的是NULL，但是我们注意刚才的步骤我们要最后把tail->next置成空指针，如果tail本身就是一个空指针就会造成一个空指针解引用的错误，所以此时我们再加一个判断，如果tail是空指针的话就直接返回NULL.

最后的程序代码：

/**
 * 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, *tail = NULL;
    while(cur)
    {
        if(cur->val != val)
        {
            if(tail == NULL)
            {
                tail = newhead = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
        	//先将需要释放的节点下一个位置保存下来，否则释放完就找不到下一个节点的位置了
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    
    //判断tail是不是空指针，是就返回NULL
    if (tail == NULL)
    {
        return NULL;
    }
	
	//将最后一个节点的末尾设置成空
    tail->next = NULL;

    return newhead;
}

1.2带哨兵位的写法

现在我来在讲一个方法。

首先我们要知道什么叫哨兵位，哨兵位就是我们手动给一个链表加一个头：



但是方法我们还是用尾插的方法。步骤和之前一样：



这样子我们返回的结构就不能是newhead,我们要返回的应该是newhead->next。

这是带哨兵位的写法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val) {
    //这里我们用malloc新开辟一个节点用来当头
    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    //新开辟的节点指向之前的第一个节点
    newhead->next = head;
    struct ListNode* tail = newhead;

    while (tail->next != NULL)
    {
        if (tail->next->val != val)
        {
            tail = tail->next;
        }
        else
        {
            struct ListNode* cur = tail->next;
            tail->next = tail->next->next;
            free(cur);
        }
    }
    return newhead->next;
}

其实看到这里，会发现代码其实简洁了不少。

二.反转一个链表

原题传送门：

力扣

题目：



如果这种题放在数组里，说不定能马上就写出来了，但是这个是链表，在链表里你用两个指针在这里遍历可行不通的。

第一题用的是链表的尾插，这里我们再试试头插。

现在我们也定义三个指针。

既然是反转那最终结果肯定就是5->4->3->2->1,然而我们第一个能拿到的只有第一个节点，为了能达到逆序的效果，我们每新取一个节点，都要放在之前节点的前面

第一步：

我们直接将第一个节点拿下来，但是会发现此时这个节点直接就指向了NULL，这样第二个节点就找不到了，所以在拿下来之前在定义一个指针next把第二个节点的位置保存下来，然后我们在更新一下newhead的位置，因为newhead是我们新链表的头，往下加一个节点，newhead肯定就要指向那个新节点。newhead更新了，cur,next就可以分别指向它们的下一个位置了：



像这样的步骤，我们放在循环里，循环结束的标志就是cur指向了末尾：



把5一下来之后，cur指向的就是NULL，此时就结束循环。

不要看我之前说的那么多，其实就几步：

第一步：把节点拿下来

cur->next = newhead;

第二步：更新头位置

newhead = cur;

第三步：cur回去指向下一个节点

cur = next;

所以这个题目的代码是：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;

    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}