链表类(Linked List)
2021/10/2 23:14:55
本文主要是介绍链表类(Linked List),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链表类总结
- 206. 反转链表
链表如何实现,如何遍历链表。链表可以保证头部尾部插入删除操作都是O(1),查找任意元素位置O(N),快慢指针和链表反转几乎是所有链表类问题的基础,尤其是反转链表,代码很短,建议直接背熟。
206. 反转链表
注:本题对递归又有了新的认知,前面学习递归的思想,更多的是不要用人脑去计算递归过程,而是用一种通用的办法直接得出答案,这种通用的过程称之为递推公式,后续部分已经完成了,只要关注第k个和第k+1个的逻辑即可!
那么本题新的认知是,递归是由递和归组成,递的过程反映的思想就是拆解成子问题的思想,归的过程就是在处理递推公式(完成指定功能),所谓的递归出口就是最小子问题的结果!。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { // 使用迭代法:充分定义好指针,这里需要三个指针,其中一个指针保存下一个节点信息,另外两个指针做好反转 // 这种链表的迭代法一般画好图,做好记录节点信息,一步一步走就可以! ListNode prev = null; ListNode cur = head; while(cur != null){ // 若curr指针不空,记录下一个节点next ListNode next = cur.next; // cur指向前者 cur.next = prev; // prev移动到cur prev = cur; // cur移动到下一个节点next cur = next; } // 最后返回最后一个节点:prev return prev; } }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { // 使用递归方式解决 // 最小子问题非递归出口 if( head == null ||head.next == null){ return head; } // 递归的递过程,这里的p实际上是最后的一个节点 ListNode p = reverseList(head.next); // 递归的归过程:递归函数,也就是递推公式的处理 // head下一个指针指向head head.next.next = head; // head的下一个指针指向null head.next = null; // 最后返回最后一个节点p return p; } }
这篇关于链表类(Linked List)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)