【Leetcode -剑指Offer 22.链表中倒数第k个结点 -203.移除链表元素】

YoungMLet

发布于 2024-03-01 09:31:28

950

发布于 2024-03-01 09:31:28

文章被收录于专栏：C++/Linux

Leetcode -剑指Offer 22.链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：给定一个链表 : 1->2->3->4->5, 和 k = 2. 返回链表 4->5.

暴力循环法

这个思路是用count计算链表的长度，返回倒数第k个结点，即是返回顺数第count-k个结点，再循环一次即可；

		struct ListNode* getKthFromEnd(struct ListNode* head, int k)
		{
		    if (head == NULL)
		    {
		        return NULL;
		    }
		
		    //计算链表的长度
		    struct ListNode* curr = head;
		    int count = 0;
		    while (curr)
		    {
		        curr = curr->next;
		        count++;
		    }
		
		    //k大于链表的长度，返回空
		    if (k > count)
		    {
		        return NULL;
		    }
		
		    //curr从头开始
		    //返回倒数第k个，即是顺数count-k个
		    curr = head;
		    for (int i = 0; i < count - k; i++)
		    {
		        curr = curr->next;
		    }
		
		    return curr;
		}

双指针

这个思路是使slow指针和fast指针相差k步，当fast走到空时，slow即是倒数的第k个结点；

例如当k等于2：初始化完成：

第一次循环完成：

最后完成：

代码：

		struct ListNode* getKthFromEnd(struct ListNode* head, int k)
		{
		    if (head == NULL)
		    {
		        return NULL;
		    }
		
		    struct ListNode* slow = head, * fast = head;
		
		    //使slow和fast相差k步
		    for (int i = 1; i <= k; i++)
		    {
		        //当到这里fast为空，证明k大于链表的长度，返回空（Leetcode这道题没有k大于链表长度的案例）
		        if (fast == NULL)
		        {
		            return NULL;
		        }
		
		        fast = fast->next;
		    }
		
		    //保证slow和fast相差k步，直到fast为空
		    while (fast)
		    {
		        slow = slow->next;
		        fast = fast->next;
		    }
		    return slow;
		}

Leetcode -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 输出：[]

递归

递归的思路是，直接找到递归的最深处，即链表的最后NULL，从后往前判断每个结点的val是否等于要移除的val，若某个结点的val等于要移除的val，就返回当前这个结点的next回去上一层；

这两句的含义如下图：

返回后上一个结点就是新的head，即如下图：

代码如下：

		struct ListNode* removeElements(struct ListNode* head, int val)
		{
		    //当链表为空时为最深处
		    if (head == NULL)
		    {
		        return NULL;
		    }
		    
		    head->next = removeElements(head->next, val);
		    return head->val == val ? head->next : head;
		}

循环法

这个思路是直接循环寻找要移除的val，下面直接看代码和注释：

		struct ListNode* removeElements(struct ListNode* head, int val)
		{
		    //把头节点等于val的直接去掉，更新头结点为原来头结点的next
		    while (head != NULL && head->val == val)
		    {
		        head = head->next;
		    }
		
		    //当head为空，返回空
		    if (head == NULL)
		    {
		        return NULL;
		    }
		
		    //curr从头开始遍历，判断curr的next的val是否等于要移除的val，是则更新curr的next；否则curr往后走
		    struct ListNode* curr = head;
		    while (curr->next)
		    {
		        if (curr->next->val == val)
		        {
		            curr->next = curr->next->next;
		        }
		
		        else
		        {
		            curr = curr->next;
		        }
		    }
		
		    return head;
		}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-02-29，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode