《剑指offer》JZ22 链表中倒数最后k个结点 JZ18 删除链表的节点

《剑指offer》JZ22 链表中倒数最后k个结点 JZ18 删除链表的节点,第1张

《剑指offer》JZ22 链表中倒数最后k个结点 JZ18 删除链表的节点

今天是12月的第一天,刷了两个题

JZ22 链表中倒数最后k个结点

题目链接

解法1 队列法(初级)

初级是因为时间复杂度O(n) 空间复杂度O(n)
思想简单:直接用数组把每一个节点存起来,输出第n-k个

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        vector res;
        while(pHead){	
            res.push_back(pHead);	//把每一个节点存起来
            pHead = pHead->next;	//遍历完整个链表
        }
        if(res.size()>=k){
            return res[res.size()-k];//如果总节点个数大于等于k,就输出倒数第k个
        }
        return nullptr;
    }
};
解法2 双指针法(进阶)

这个就好一些了:时间复杂度O(n)空间复杂度O(1)
思想稍微难一些:

  1. 用两个指针指向头节点,先让走得快的指针移动k步
  2. 两个指针一次走一步,直到走得快的先走完整个链表
  3. 走的满的指针即为所求(倒数第k个)

其中的思想核心就是让两个指针的相对位置永远相差k,当后面的指针指向队尾的后面,前面的指针就是指向倒数第k个。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* fast=pHead;ListNode* slow=pHead;
        for(int i=0;inext;
        }
        while(fast){		//保持k的相对距离直到结尾
            fast=fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
JZ18 删除链表的节点

这个题挺简单,数据结构老师也详细讲过。
链表删除节点的本质就是,让当前要删除的结点的前面那个结点的next,指向当前结点的next。当前节点就被绕过去了,也就是从链表上被删除了。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* tmp = head;
        ListNode* last = head;
        if(head->val==val) return head->next;
        tmp = tmp->next;
        while(tmp){
            if(tmp->val==val){
                last->next = tmp->next;   //核心语句,解释在上面
                return head;
            }
            tmp=tmp->next;
            last=last->next;
        }
        return head;
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5638235.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存