T876链表的中间节点——Java实现
2021/12/15 22:11:51
本文主要是介绍T876链表的中间节点——Java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
T876题目描述
给定一个头结点为 head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
解题过程
解法一
思路
-
使用常规方法,也就是先遍历链表获得链表长度,随后获得中间结点的下标,再次遍历链表到中间节点位置,返回该节点即可
-
设链表的长度为
size
,需要注意的是不需要考虑链表长度的奇偶性,因为当长度为偶数时,返回的是size/2+1
,长度为奇数时,返回的是size/2+1
,是一样的 -
时间复杂度为
O(n)
实现代码
public ListNode middleNode(ListNode head) { ListNode curNode = head; int size = 0; while(curNode!=null){ size++; curNode = curNode.next; } curNode = head; //因为head不为null,所以count初始值为1 int count = 1; while(count < size/2+1){ curNode = curNode.next; count++; } return curNode; }
解法二
思路
-
使用快慢指针
a
,b
-
a指针
每次只走一步,b指针
每次只走两步 -
等到
b指针
无法在移动的时候,a指针
已经指向目标节点 -
注意,不管链表长度的奇偶性如何…代码解释…
public ListNode middleNode(ListNode head) { //firstNode指针走两步 ListNode firstNode = head; //lastNode指针走一步 ListNode lastNode = head; //跳出循环时,firstNode指针已经指向null或者firstNode.next指针已经指向null //这里大家可以使用手指验算,很容易想通的 //只不过要注意的是,是从第一根手指开始走哦 //也就是说第一次走完之后,firstNode指针应该指向第三根手指 while(firstNode!=null && firstNode.next != null){ lastNode = lastNode.next; firstNode = firstNode.next.next; } return lastNode; }
这篇关于T876链表的中间节点——Java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现