【Leetcode】拿捏链表（一）——206.反转链表、203.移除链表元素

作者：一个喜欢猫咪的的程序员

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

---

目录

206.反转链表 

203.移除链表元素

---

206.反转链表 

力扣https://leetcode.cn/problems/reverse-linked-list/题目描述：

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

---

 示例：

示例 1：

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

 示例 2：

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

示例 3：

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

---

思路：

思路一：头插法

设一个变量cur遍历整个链表，并且创建一个新的链表rhead我们将cur一个一个头插进去，但这样会找不到cur的下一个位置，因此我们提前设一个变量next来找cur的下一个位置。

时间复杂度：O（N）                                                            空间复杂度：O（1） 

思路二：递归法

利用递归找到最后一个位置，让他倒置

需要注意的是 n1​ 的下一个节点必须指向空。如果忽略了这一点，链表中可能会产生环。

时间复杂度：O（N）                                                            空间复杂度：O（N） 

---

代码实现：

思路一：头插法

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

思路二：

struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode*newhead=reverseList(head->next);
    head->next->next=head;
    head->next=NULL;
    return newhead;
}

---

203.移除链表元素

力扣https://leetcode.cn/problems/remove-linked-list-elements/题目描述：

给你一个链表的头节点 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
输出：[]

---

思路：

思路一：尾插迭代法

利用创建一个新的链表newhead，利用cur如果cur->val=val时，让这个cur下来到newhead，否则删掉。

 时间复杂度：O（N）                                                    空间复杂度：O（1）

---

思路二:递归法

对于给定的链表，首先对除了头节点 head以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 va。如果 head 的节点值等于va，则head 需要被删除，因此删除操作后的头节点为 head，next如果head的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是 head。上述过程是一个递归的过程。

递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除head。

作者：LeetCode-Solution
来源：力扣（LeetCode）

时间复杂度：O（N）                                                    空间复杂度：O（N）

---

代码实现：

思路一：尾插迭代法

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

思路二：递归法：

struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL) {
        return head;
    }
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}