链表拾遗笔记

2024-05-23 06:48
文章标签 链表 笔记 拾遗

本文主要是介绍链表拾遗笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 1. 反转单链表
    • 2. 打印单链表
    • 3. O(1)删除指定节点
    • 4. 双指针法求求链表倒数第k个节点
    • 5. 判断链表是不是有环
    • 6. 合并两个单链表
    • 7. 删除链表中的重复节点
    • 7. 实现一个单链表
    • 总结

提示：以下是本篇文章正文内容，下面案例可供参考

1. 反转单链表

    /*** 递归 https://blog.csdn.net/qq_33958946/article/details/84326965** <p>* 如果当前节点或者当前节点的下一节点为空，直接返回该节点；* 否则使该节点的后一节点指向该节点，以此递归。*/public static ListNode reverseList3(ListNode head) {if (head == null || head.next == null) return head;ListNode nextNode = head.next; //得到当前节点的下一节点head.next = null; //打断当前指针链ListNode res = reverseList3(nextNode); //每次递归下一节点进行反转nextNode.next = head;//反转指针域return res;}// 迭代方式public static ListNode reverseList(ListNode curr) {ListNode prev = null;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}

2. 打印单链表

    public static void printList(ListNode node) {if (node == null) return;if (node.next != null) {System.out.print(node.val + "->");} else {System.out.println(node.val);}printList(node.next);}

3. O(1)删除指定节点

//    题目：给定一个链表和一个节点指针，在O（1）时间删除该节点。
//    方法：用后一个节点数据覆盖要删除的节点，然后删除下一个节点。public void deleteNode(ListNode node) {node.val  = node.next.val;node.next = node.next.next;}public static void main(String[] args) {ListNode n1 = new ListNode(3);ListNode n2 = new ListNode(5);ListNode n3 = new ListNode(7);ListNode n4 = new ListNode(2);n1.next = n2;n2.next = n3;n3.next = n4;// 删除节点 n2deleteNode(n2);printList(n1); // 3->7->2}

是不是很神奇😄

4. 双指针法求求链表倒数第k个节点

给定一个单向链表，要求找出该链表中倒数第 k 个节点，要求只能遍历一次链表，且空间复杂度为 O(1)。

我们定义两个指针，分别叫前指针和后指针。
先让前指针指向链表的头指针并开始遍历向前走k-1,后指针保持不动。
从第k步开始，后指针也开始从链表的头指针开始遍历。
由于两个指针的距离保持在k-1,当前指针到达链表的尾结点时，后指针正好是倒数第k个结点。

public static ListNode FindKthToTail(ListNode head, int k) {if (head == null || k <= 0) {return null;}//定义两个指针，一个前指针(p1)和一个后指针(p2)ListNode p1 = head;ListNode p2 = head;//p1先前走k-1步for (int i = 0; i < k - 1; i++) {//表示k大于链表长度，返回空if (p1 == null) {return null;}p1 = p1.next;}if (p1 == null) {return null;}//快慢指针同时往后遍历while (p1.next != null) {p1 = p1.next;p2 = p2.next;}return p2;}

引用：https://blog.csdn.net/qq_35462323/article/details/108326708


5. 判断链表是不是有环

判断是否成环：使用快慢指针遍历链表：

慢指针：从头节点开始，一次跳一个节点。
快指针：从头节点开始，一次跳两个节点。

如果是成环的，这两个指针一定会相遇。

// 示例 1public static boolean hasLoop(ListNode n) {//定义两个指针p1,p2ListNode p1 = n;ListNode p2 = n.next;while (p2 != null) {p1 = p1.next;  //每次迭代时，指针1走一步，指针2走两步p2 = p2.next.next;if (p2 == null) return false;//不存在环时，退出if (p1.val == p2.val) return true;//当两个指针重逢时，说明存在环，否则不存在。}return true; //如果p2为null，说明元素只有一个，也可以说明是存在环}
// 示例 2 通俗易懂private static boolean isCyc(Node node){Node slow = node;Node fast = node;while (slow != null && fast != null){slow = slow.next;fast = fast.next.next;if(slow == fast)return true;}return false;}

原文链接：https://blog.csdn.net/ningmengbaby/article/details/101229923

6. 合并两个单链表

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}

链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/


7. 删除链表中的重复节点

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3

      public static void main(String[] args) {ListNode list = ListUtil.getList();ListUtil.printList(list);ListUtil.printList(deleteDuplicates(list));
//        1->2->2->4->5
//        1->2->4->5}public static ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}head.next = deleteDuplicates(head.next);if (head.val == head.next.val) {head = head.next;}return head;}

/*** @DESC 定义节点* @Author tzq* @Date 2019-08-17 18:30**/
public class Node {public Node next;public int data;public Node(int data) {this.data = data;}public void display() {System.out.print(data + " ");}
}

链接：https://blog.csdn.net/xushibi4580/article/details/90354394


7. 实现一个单链表

public class LinkList {Node first; //头结点int pos = 0; //节点的位置从0开始（链表无下标概念）public LinkList() {this.first = null;}public void addFirstNode(int data) {Node node = new Node(data);node.next = first;first = node;}public Node removeFirstNode() {Node tmp = first;first = tmp.next;return tmp;}// 任意位置插入节点public void add(int index, int data) {if (index > getListLength()) {throw new MyException("插入位置越界！");}Node node = new Node(data);Node current = first;Node pre = first;while (pos != index) {pre = current;current = current.next;pos++;}node.next = current;pre.next = node;pos = 0;}//显示所有节点值public void displayAllNode() {Node current = first;while (null != current) {current.display();current = current.next;}}//打印链表长度public int getListLength() {Node curr = first;int num = 0;while (null != curr) {num++;curr = curr.next;}return num;}//根据位置查找Nodepublic Node findByPos(int index) {if (index > getListLength()) {throw new MyException("查找位置越界，不存在该元素！");}Node current = first;while (pos != index) {current = current.next;pos++;}return current;}
}

定义Node节点：

/*** @DESC 定义节点* @Author tzq* @Date 2019-08-17 18:30**/
public class Node {public Node next;public int data;public Node(int data) {this.data = data;}public void display() {System.out.print(data + " ");}
}

总结

未完待续…

这篇关于链表拾遗笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/996148。

相关文章

csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
论文阅读笔记: Segment Anything

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2
阅读更多...
【C++学习笔记 20】C++中的智能指针

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别，使用new关键字创建变量时，需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时，不必自己去调用delete，甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针，是一种作用域指针，意思是当指针超出该作用域时，会自动调用delete。它名为unique的原因是这个
阅读更多...
查看提交历史 —— Git 学习笔记 11

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新，又或者克隆了某个项目之后，你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2