【LeetCode训练营】反转链表 移除链表元素 详细图解 203,206

移除链表元素

203. 移除链表元素

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

示例 1：

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

输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1

输出：[]

示例 3：

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

输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内

1 <= Node.val <= 50

0 <= val <= 50

思路

题目思路：要移除值为val的元素，就涉及到了单链表的头删和中间位置删除，这就需要我们定义一个prev指针指向要删除元素的前一个元素，然后让它指向要删除元素的后一个元素。

prev指针一开始定义为NULL，当链表当前位置即为要删除元素的位置且prev指针为空时，就需要用到单链表头删的知识来考虑这一种情况。

不需要删除的情况就让prev指针指向tail指针的位置，让tail指向下一个位置。

需要删除且不为头删时，写法就是单链表中间删除的写法，让前一个指针指向删除位置的下一个，把要删除的位置free掉即可。

源码

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

反转链表

206. 反转链表

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

示例 1：

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

输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]

输出：[2,1]

示例 3：

输入：head = []

输出：[]

提示：

链表中节点的数目范围是 [0, 5000]

-5000 <= Node.val <= 5000

思路

反转单链表，我采用头插法，对每一个结点采用头插。

定义一个中间变量temp，将cur->next赋值给它，保存它的值，便于一会使用。

定义一个pre为空，让cur->next指向它。一开始的情况是这样的。

之后我们将cur的值赋给pre，让cur指向它的下一个。

可它的next已经变成pre了，没法直接 cur=cur->next。

这是我们上面定义的temp就派上用场了。

将temp的值赋给cur。

这时的情况变成了这样。

这样到最后，情况会变成这样。

所以循环的条件应该是while(cur)。

源码

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

如果大家有更好的方法，请一定要私信教教我！求大佬带带。