【LeetCode】单链表——刷题

你曾经灼热的眼眶，是人生中少数的笨拙又可贵的时刻。

文章目录

1.反转单链表

题目思路及图解 

代码中需要注意的问题

2.移除链表元素

题目思路及图解

代码中需要注意的问题

---

  大家好，我是纪宁。

  这篇文章分享给大家一些经典的单链表leetcode笔试题的解法。

  先导知识：数据结构——单链表

1.反转单链表

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

题目思路及图解 

   思路：将单链表的每个结点的指针域从前到后逐个变向，整体上看就是将单链表反向。

  定义三个结构体变量 n1，n2，n3，其中 n1，n2 用来改变结点指向，n3用来存储当前结点的下一个结点的地址，即当前结点的 next  

  改变指向图解，初始情况下，n1指向空，n2指向第一个结点，n3指向第二个结点。

​
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    if(n2!=NULL)
         n3 = n2->next;
    while (n2!= NULL)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3!=NULL)
            n3 = n3->next;
    }
    return n1;
}

代码中需要注意的问题

1.当传进来结点为空的时候，不能让 n3 = n2 -> next，因为n2没有下一个结点。

2.要先改变指向，再将n1，n2，n3 进行前移。因为开始结点翻转后就变成了尾结点，尾结点的 next 必须指向NULL。

3.当n1，n2，n3前移时，要对 n3 是否为NULL进行判断。因为判定循环结束是当 n2 移动到 NULL 的时候，在这之前，n3 会先一步达到NULL，是时候就要进行判断，如果n3已为NUL的时候，就不能再让 n3 前移，否则会出现越界情况。

2.移除链表元素

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

题目思路及图解

思路：删除一个结点，要知道这个结点前一个结点的信息和下一个结点的信息，那么就必须定义两个结构体指针变量，一个指向当前结点，一个指向这个结点的前一个结点。

  定义一个指针变量 prev，负责指向前一个结点，先让它指向 NULL ；定义一个指针变量 cur ，负责指向当前结点，先让它指向头结点

  常规情况下（要删除的结点在中间或末尾），只需要当 cur-> val 的值等于 val 时，让 cur 指向 cur 的下一个结点，再释放原来的空间即可，只需要保证 prev 一直在 cur 的后面跟着。

   当第一个结点就是要删除结点的时候，就需要移动头结点了。当找到第一个不等于 val 的结点的时候，再将 cur 的值赋给 prev，prev 才能开始移动第一次移动，接着 cur 再向前移动。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur=head;
    struct ListNode*prev=NULL;
    while(cur!=NULL)
    {
        if(cur->val==val)
        {
             if(head->val==val)
             {
                 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;
}

代码中需要注意的问题

  当需要删去某个结点的时候，将 prev 的下一个结点赋值为要删除结点的下一个结点，再释放这个结点的空间，就能做到将要删结点的前一个和后一个连起来。

  当不需要删去某个结点，正常遍历链表时，每次先将prev的值赋为cur，再将cur 指向下一个结点（ cur = cur -> next ），这样就做到了prev与 cur 一起前进，且 prev 一直在 cur 的前一个结点处。