关于链表的题目—leetcode

2023-10-27

第一题：删除链表中的指定节点

问题描述：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

题目接口：

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


struct ListNode* deleteNode(struct ListNode* head, int val){

}

问题解答思路：

这道题的意思就是要删除链表中的值等于val的节点，但是这道题需要考虑两种情况。

第一种情况就是删除头节点，第二种情况就是删除不是头节点的情况。这两种情况可是不一样的，假如我们把这两种情况混为一谈这道题是不一定能通过的。所以我们要分两种情况来解决这道题。

解法1：分头节点与一般节点两种情况

struct ListNode* deleteNode(struct ListNode* head, int val){
        while(head!=NULL&&head->val==val){//处理头节点的问题
            struct ListNode*temp = head;
            head = head->next;//移动head删掉头节点
            free(temp);
        }
        struct ListNode*temp = head;
        struct ListNode*cur = head->next;//因为头节点已经处理完了，所以再让cur指向head是没有意义的，所以让cur指向第二个节点
        while(cur){
            if(cur->val==val){
             temp->next = cur->next;//删除值为val的节点
             cur = cur->next;//再次移动cur
            }
            else{
                temp = cur;//记录cur的原来位置
                cur = cur->next;//cur向下一位移动
            }

        }
return head;
}

解法2：加一个节点在头节点前面

思路：既然第一种解法要我们处理两种情况，那我们可不可以把这两种解法换成一种解法呢？当然可以，只要我们人为的创建一个节点就可以将将头节点的情况去掉了。

虚拟头节点法：

struct ListNode* deleteNode(struct ListNode* head, int val){
    struct ListNode* dumy = (struct ListNode*)malloc(sizeof(struct ListNode));//使用malloc搞出来一个虚拟节点。
    struct ListNode* cur = head;
    struct ListNode* temp = dumy;
    dumy->next = head;//将dump连接在head的前面，是dumy成为一个头节点
    while(cur){//第一种方法中的普通节点处理法，这次就要从head开始删除了。
        if(cur->val==val){
            temp->next = cur->next;
            cur = cur->next;
            temp = cur;

        }
        else{
            temp = cur;
            cur = cur->next;
        }

    }
head = dumy->next;//返回值是dumy->next。这一点要注意
free(dumy);//释放掉dumy,防止内存泄漏
return head;//返回头节点。

}

解法三：尾插法

对于愚笨的我来说，这种方法是我最难理解的，那我就在这里重点讲解一下吧。

首先来看一下代码:

尾插法代码：

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

}

尾插法解法过程演示：

首先我们要明确的是，不论这道题怎么写这道题都有三种情况要处理。即：删除头节点，删除中间节点，删除尾节点。

1.删除头节点：

假如我们的链表是：-3->5->99，要删除的值是-3，也就是要删除头节点

现在我们看看代码是如何走的：下面代码是删除头节点时的执行代码

 struct ListNode* cur  = head;
    struct ListNode* tail = NULL;
    struct ListNode* newnode = NULL;
 else{
            struct ListNode*  del = cur;
            cur = cur->next;
            free(del);
        }

这段代码执行以后：

tail,newnode,cur三者与链表的关系就变成这样了：

然后我们就不用删除头节点了，剩下的节点的处理方式就是下面代码：

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

现在，因为tail节点指向空，cur->val!=val。所以执行第二个if语句。

但是此时tail还是要与cur指向的下一个元素有联系。其实这也可以把tail看作是cur的一个拷贝，既然是拷贝tail指向的下一个节点当然就是cur指向的下一个节点了。

代码

  cur = cur->next;
  tail->next = NULL;

再来看看这一段代码的示意图：

在这里可以看到在执行了cur=cur->next的操作以后，将tail的next置空的操作。这是要特别注意的一点。因为这样的操作可以避免野指针的问题。当然还有一点需要注意的就是这两个代码执行顺序的问题。如果先执行tail->next = NULL的操作，再执行cur = cur->next的操作将会导致栈溢出的问题。原因很简单，因为tail与cur一开始指向的是同一块空间，假如先置空tail的next，cur将找不到自己的next。

最后，执行以下代码：

else{
       tail->next = cur;
       tail = tail->next;
            }
            cur = cur->next;
            tail->next = NULL;

最后再返回newnode，就得到我们想要得到的结果了。

return newnode;

其它的情况这个代码也是可以过的，在这里就不啰嗦了。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

链表题目

那些曾经不会的题目

Ledcode刷题

链表

LeetCode