【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #

简介: 【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #

前言


  • 对于单链表的OJ练习,需要深刻理解做题的思路,这样我们才能够在任何场景都能够熟练的解答有关链表的问题。
  • 关于OJ练习(1):->传送门<-,其题目较为简单,思路也好理解,本章与(1)差不多,难度不大,核心点就在于理解解题思路。


链表的中间结点


题目链接:->传送门<-


  • 该题目描述为:给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。


1.如果节点数为奇数,这个中间节点就显而易见了。(3)


2593f55035134933bfbdca16a0d8b974.png

2.如果节点数为偶数,这里认为中间两个节点的第二个节点为中间节点。(4)


ec275193467e4d85be6758069397fcc6.png


思路一:


我们可以先遍历一遍链表,统计一下链表节点的个数。


然后将这个个数除以二加一(count / 2 + 1)便是中间这个节点的位置。


当然,我们在循环寻找这个中间节点的时候,是从头节点开始的,因此循环只需要循环((count / 2 + 1) - 1)即可。


代码实现:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* cur = head;
    int count = 0;
    while (cur)
    {
        count ++ ;
        cur = cur->next;
    }
    count = count / 2 + 1;
    while (-- count) // 循环count - 1次
    {
        head = head->next;
    }
    return head;
}


思路二:


该做法为快慢指针。


啥为快慢指针呢?在本题有关当中,我们定义两个指针指向链表的头节点,并且共同遍历链表,不同的是,一个指针每一次走两步,另一个指针每次走一步,这就是快慢指针。


每当快指针满足循环结束条件,慢指针都是指向链表的中间节点的。因为快指针走两步,慢指针走一步,整个移动的位移差相差一倍,所以每当快指针满足结束条件的时候,慢指针走的步数都是快指针走的步数的一半, 因此慢指针指向的那个节点就是整个链表的中间节点。


快指针结束的条件有两种情况,一种是快指针刚好指向空结束,一种是快指针指向尾节点结束,也就是快指针的next为NULL。


1.当快指针刚好指向NULL结束,此时链表的节点个数为偶数:


b67895822f834005a7625e360c8200c9.gif

2.当快指针指向尾节点结束,也就是快指针的next为NULL,此时链表的节点个数为奇数:


a430d71ec70641f6a35deb65a7870f63.gif

代码实现:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}


注意:

while循环的判断条件,fast一定要在前面,这是因为:判断是从左到右判断的,如果fast->next在前,而此时链表的结点的个数为偶数,那么fast就会直接到达NULL,这时候对空指针解引用操作就出问题了。


链表中倒数第k个结点


题目链接:->传送门<-

  • 该题目描述为:输入一个链表,输出该链表中倒数第k个结点。。


49dfc5d2c1a2457eb40d4f52eb5122fd.png


思路一:


既然是倒数第k个,那我们就看看是正数的第几个。


先遍历一遍单链表,统计一下链表的结点个数(count),通过数学知识,可得倒数的第k个结点就是正数的第count - k + 1个节点,这时只要在遍历一次链表,找到第count - k + 1个节点返回即可。


当然,这里嘚注意k是不是大于链表节点的个数的情况。


代码实现:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* cur = pListHead;
    int count = 0;
    // 统计链表节点的个数
    while (cur)
    {
        count ++ ;
        cur = cur->next;
    }
    // 如果k大于链表的节点个数,直接返回NULL
    if (k > count) return NULL;
    int tmp = count - k;
  // 由于从头个节点开始算,因此只需要循环count - k次就可以找到倒数第k个节点
    while (tmp -- )
    {
        pListHead = pListHead->next;
    }
    return pListHead;
}



思路二:


同样是快慢指针,这里的快慢指针解法是:快指针先向后走k步或者先向后走k - 1步,然后快指针与慢指针同时向后走,当快指针满足循环结束条件停止,此时慢指针指向的节点就是倒数第k个节点。

1.如果快指针先向后走k步,此时快指针与慢指针之间相差k步,因此,当快指针到达NULL时,此时慢指针刚好指向倒数第k个节点。(倒数第k个节点与NULL相差k步)(循环结束条件:fast == NULL)


19cd3f81edca44ef835831189bc23155.gif

2.如果快指针先向后走k - 1步,此时快指针与慢指针之间相差k - 1步,然后快指针与慢指针同时向后走,当快指针满足循环结束条件停止,此时慢指针指向的节点就是倒数第k个节点。(倒数第k个节点与尾节点相差k - 1步)(循环结束条件:fast->next == NULL)


54901dae52c74be1b5648974653ce5dd.gif

代码实现:(这里只实现fast先走k步的情况,fast先走k - 1的情况大同小异)

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow = pListHead, * fast = pListHead;
    // fast先走k步
    while (k -- )
    {
        if (!fast) return NULL; // 如果k还没为0但fast已经指向空了,说明k大于链表的结点的个数,此时直接返回NULL
        fast = fast->next;
    }
  // 当fast为NULL时结束循环
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}


写在最后

对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。


感谢阅读本小白的博客,错误的地方请严厉指出噢!

相关文章
|
18天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
52 1
|
19天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
21天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
23 7
|
2月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
4月前
【数据结构OJ题】环形链表
力扣题目——环形链表
36 3
【数据结构OJ题】环形链表
|
4月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
51 1
【数据结构OJ题】复制带随机指针的链表
|
4月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
28 1
【数据结构OJ题】环形链表II
|
4月前
【数据结构OJ题】相交链表
力扣题目——相交链表
32 1
【数据结构OJ题】相交链表
|
4月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
39 8
【数据结构OJ题】合并两个有序链表
|
4月前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
40 2
【数据结构OJ题】移除链表元素