【拿捏链表(Ⅰ)】—作为程序员必须会的链表经典题目

简介: 【拿捏链表(Ⅰ)】—作为程序员必须会的链表经典题目

目录


反转链表

链表中倒数第k个结点

删除链表中的节点

反转链表


题目:该题是力扣中的一道关于链表的简单经典题目。如下:


1.png


思路:我们可以这么来想,假如正常尾插1 2 3 4 5的话,链表就是当前的1->2->3->4->5->NULL,但是假如我们将1 2 3

4 5进行头插的话,就会变成:5->4->3->2->1->NULL。所以,这里我们采用头插法进行反转。原理如下图:


2.gif

代码实现:


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*cur=head;
    struct ListNode*prev=NULL;//新头节点
    //取节点头插
    while(cur!=NULL)
    {
        struct ListNode*Next=cur->next;//下一个节点
        cur->next=prev;
        prev=cur;
        cur=Next;
    }
    //返回新节点
    return prev;//假如是个空表,prev==NULL依然适用
}


链表中倒数第k个结点



3.png4.gif


思路:对于这道题,我们可能上来就会想到:先统计节点的个数n,然后再走n-k步,就可以走到倒数第k个位置,这个方法肯定是可行的。不过这里我要讲的是另一种思路:快慢指针法

即:我们可以定义fast与slow两个指针,fast指针先走k步,然后再让slow与fast同时走,当fast走到NULL时,slow就处在倒数第k个位置。如下:

代码实现:


struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    //先走k步
    while(k--)
     {
         //空链表,或者k过大
        if(fast == NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    //同时继续往后走,slow走了n-k步
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    //返回slow
    return slow;
}


删除链表中的节点


5.png

思路:这里我们需要注意,题目中明确说明node不是最后一个节点,并且也说了,只是让node节点的值不存在与这个链表,并且链表总结点-1.还要保持前后的值的顺序不变。

不要小看这些提示,它会使我们更容易入手。我们可以这么来搞:我们把node后面节点的值赋给node节点,然后让node指向它后面的后面的节点,最后再释放node的下一个节点。就可以保证以上所有要求!如下:


6.gif


代码实现:


void deleteNode(struct ListNode* node) {
    struct ListNode*next=node->next;//记录node的下一个节点
    node->val=next->val;//赋值
    node->next=next->next;//node的下一个节点指向next的下一个节点
    free(next);//释放next
}


题目倒是挺长的,但理解后其实没啥,切记一定要多画图,有助于理解!


相关文章
|
算法 索引
带你拿捏链表
带你拿捏链表
124 0
【LeetCode题目详解】(三)21.合并两个有序链表、141.环形链表、142.环形链表Ⅱ
【LeetCode题目详解】(三)21.合并两个有序链表、141.环形链表、142.环形链表Ⅱ
103 0
|
测试技术
【LeetCode题目详解】(二)206.反转链表、876.链表的中间结点
【LeetCode题目详解】(二)206.反转链表、876.链表的中间结点
82 0
|
1月前
|
存储
链表题目练习及讲解(下)
链表题目练习及讲解(下)
25 9
|
1月前
链表题目练习及讲解(上)
链表题目练习及讲解(上)
23 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
5月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
6月前
题目----力扣--移除链表元素
题目----力扣--移除链表元素
41 1
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
5月前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II