AI 助理
备案控制台
开发者社区 人工智能 文章 正文

java单链表常用操作

2016-05-19 2647
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

总结提高，与君共勉

概述、

数据结构与算法亘古不变的主题，链表也是面试常考的问题，特别是手写代码常常出现，将从以下方面做个小结

【链表个数】

【反转链表-循环】

【反转链表-递归】

【查找链表倒数第K个节点】

【查找链表中间节点】

【判断链表是否有环】

【从尾到头打印单链表-递归】

【从尾到头打印单链表-栈】

【由小到大合并有序单链表-循环】

【由小到大合并有序单链表-递归】


通常在Java中这样定义单链表结构

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">class Node{  
  2.     int value;  
  3.     Node next;  
  4.     public Node(int n){  
  5.         this.value = n;  
  6.         this.next = null;     
  7.     }  
  8. }  
  9. </span>  


1、链表个数

这个比较简单，不再赘述

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">    // 求单链表的结点个数  
  2.     public int getListLen(Node head) {  
  3.         int len = 0;  
  4.         while (head != null) {  
  5.             len++;  
  6.             head = head.next;  
  7.         }  
  8.         return len;  
  9.     }</span>  


2、反转链表-循环

采用双指针，主要是4行代码，其中2,3俩行完成指针反转，1,4主要是保持head往下指

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 反转单链表(循环)  
  2.     public Node reverseList(Node head) {  
  3.         // 安全性检查  
  4.         if (head == null || head.next == null)  
  5.             return head;  
  6.         Node pre = null;  
  7.         Node temp = null;  
  8.         while (head != null) {  
  9.             // 以下1234均指以下四行代码  
  10.             temp = head.next;// 与第4行对应完成头结点移动  
  11.             head.next = pre;// 与第3行对应完成反转  
  12.             pre = head;// 与第2行对应完成反转  
  13.             head = temp;// 与第1行对应完成头结点移动  
  14.         }  
  15.         return pre;  
  16.     }</span>  


3、反转链表-递归

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 将单链表反转,递归  
  2.     public static Node reverseListRec(Node head) {  
  3.         if (head == null || head.next == null)  
  4.             return head;  
  5.         Node reHead = reverseListRec(head.next);  
  6.         head.next.next = head;  
  7.         head.next = null;  
  8.         return reHead;  
  9.     }</span>  


4、查找链表倒数第K个节点

双指针法，不多解释

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 查找单链表倒数第K个结点 双指针法  
  2.     public Node reKNode(Node head, int k) {  
  3.         if (head == null)  
  4.             return head;  
  5.         int len = getListLen(head);  
  6.         if (k > len)  
  7.             return null;  
  8.         Node targetK = head;  
  9.         Node nextK = head;  
  10.         // 先走到K个位置  
  11.         for (int i = 0; i < k; i++) {  
  12.             nextK = nextK.next;  
  13.         }  
  14.         // 再和头结点一起走，nextk走到结尾，此时targetk为倒数第K个节点  
  15.         while (nextK != null) {  
  16.             nextK = nextK.next;  
  17.             targetK = targetK.next;  
  18.         }  
  19.         return targetK;  
  20.     }</span>  


5、查找链表中间节点

快慢指针，不多解释

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">public Node getMid(Node head) {  
  2.         // 类似的快慢指针法  
  3.         // 安全性检查  
  4.         if (head == null || head.next == null)  
  5.             return head;  
  6.         Node target = head;  
  7.         Node temp = head;  
  8.         while (temp != null && temp.next != null) {  
  9.             target = target.next;  
  10.             temp = temp.next.next;  
  11.         }  
  12.         return target;  
  13.     }</span>  


6、判断链表是否有环

主要还是快慢指针，如果快的指针能够追上慢指针则有环

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 判断一个单链表中是否有环,快慢指针  
  2.     public boolean hasCycle(Node head) {  
  3.         boolean flag = false;  
  4.         Node p1 = head;  
  5.         Node p2 = head;  
  6.         while (p1 != null && p2 != null) {  
  7.             p1 = p1.next;  
  8.             p2 = p2.next.next;  
  9.             if (p2 == p1) {  
  10.                 flag = true;  
  11.                 break;  
  12.             }  
  13.         }  
  14.         return flag;  
  15.     }</span>  


7、从尾到头打印单链表-递归

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 从尾到头打印单链表(递归)  
  2.     public void reList1(Node head) {  
  3.         // 安全性检查  
  4.         if (head == null)  
  5.             return;  
  6.         else {  
  7.             reList1(head.next);  
  8.             System.out.println(head.value);  
  9.         }  
  10.   
  11.     }</span>  


8、从尾到头打印单链表-栈

利用栈FILO的性质，先存储节点然后输出每个栈的节点值

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 从尾到头打印单链表（栈）  
  2.     public void reList2(Node head) {  
  3.         Stack<Node> s = new Stack<Node>();  
  4.         while (head != null) {  
  5.             s.push(head);  
  6.             head = head.next;  
  7.         }  
  8.         while (!s.isEmpty()) {  
  9.             System.out.println(s.pop().value);  
  10.         }  
  11.     }</span>  


9、由小到大合并有序单链表-循环

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">    // 由小到大合并俩个有序的单链表(循环)  
  2.     public Node mergeSort1(Node head1, Node head2) {  
  3.         // 安全性检查  
  4.         if (head1 == null)  
  5.             return head2;  
  6.         if (head2 == null)  
  7.             return head1;  
  8.         // 新建合并节点  
  9.         Node target = null;  
  10.         // 确定第一个元素的节点  
  11.         if (head1.value > head2.value) {  
  12.             target = head2;  
  13.             head2 = head2.next;  
  14.         } else {  
  15.             target = head1;  
  16.             head1 = head1.next;  
  17.         }  
  18.         target.next = null;  
  19.         // 开始合并  
  20.         Node mergeHead = target;  
  21.         while (head1 != null && head2 != null) {  
  22.             // 当两个链表都不为空  
  23.             if (head1.value > head2.value) {  
  24.                 target.next = head2;  
  25.                 head2 = head2.next;  
  26.             } else {  
  27.                 target.next = head1;  
  28.                 head1 = head1.next;  
  29.             }  
  30.             target = target.next;  
  31.             target.next = null;  
  32.         }  
  33.         if (head1 == null)  
  34.             target.next = head2;  
  35.         else  
  36.             target.next = head1;  
  37.         return mergeHead;  
  38.   
  39.     }</span>  


10、由小到大合并有序单链表-递归

[java]  view plain  copy
  1. <span style="font-family:Microsoft YaHei;font-size:14px;">// 由小到大合并俩个有序的单链表(递归)  
  2.     public Node mergeSort2(Node head1, Node head2) {  
  3.         if (head1 == null)  
  4.             return head2;  
  5.         if (head2 == null)  
  6.             return head1;  
  7.         if (head1.value > head2.value) {  
  8.             head2.next = mergeSort2(head2.next, head1);  
  9.             return head2;  
  10.         } else {  
  11.             head1.next = mergeSort2(head1.next, head2);  
  12.             return head1;  
  13.         }  
  14.     }</span>  


转载：http://blog.csdn.net/xsf50717/article/details/47375437

文章标签：
Java
算法
存储
关键词：
Java单链表
Java常用操作
shy丶gril
目录
相关文章
星辰醉天河ii-25383
|
9月前
|
Java 计算机视觉 Spring
Java 文件常用操作与流转换
Java 文件常用操作与流转换
星辰醉天河ii-25383
232 0
杀死一只知更鸟debug
|
5月前
|
存储 Java
java数据结构，线性表链式存储（单链表）的实现
文章讲解了单链表的基本概念和Java实现，包括头指针、尾节点和节点结构。提供了实现代码，包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作，如添加、删除、更新和查找元素，并总结了操作的时间复杂度。
杀死一只知更鸟debug
82 1
java数据结构，线性表链式存储（单链表）的实现
lingeringfear
|
存储 安全 Java
Java集合Map之HashMap常用操作
在我看来 , 链表是为了解决hash碰撞使用的一种方法 : 拉线法 , 而红黑树是为了解决&quot;拉的这个线&quot;(链表存储的元素太多)过长的话元素遍历慢的问题
lingeringfear
76 2
HannYang
|
Rust 自然语言处理 Java
单链表的多语言表达：C++、Java、Python、Go、Rust
单链表是一种链式数据结构，由一个头节点和一些指向下一个节点的指针组成。每个节点包含一个数据元素和指向下一个节点的指针。头节点没有数据，只用于表示链表的开始位置。单链表相对于数组的优点是插入和删除元素时不需要移动其他元素，时间复杂度为O(1)。但是，在查找元素时，单链表比数组要慢，时间复杂度为O(n)。
HannYang
16667 7
碳基肥宅
|
9月前
|
Java
DAY-1 | Java数据结构之链表：删除无头单链表中等于给定值 val 的所有节点
力扣203题解：使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre，记录cur的前一个节点，遍历链表时，若cur.val!=key，pre和cur同时前进；若cur.val==key，则pre.next=cur.next，cur继续前进，确保pre不急于跟随以处理连续相同值的情况。遍历结束后，处理头节点可能需要删除的特殊情况。
碳基肥宅
57 0
请回答1024
|
9月前
|
存储 Java
Java 实现单链表
Java 实现单链表
请回答1024
63 0
云水闲
|
9月前
|
存储 Java
Java实现单链表
Java实现单链表
云水闲
72 0
极客李华
|
9月前
|
Java C++
单链表（Java每日一题）
单链表（Java每日一题）
极客李华
55 0
梳中分的坤坤
|
存储 Java
图解Java数据结构之单链表
图解Java数据结构之单链表
梳中分的坤坤
103 0
HelloDam
|
存储 Java
一篇文章入门单链表+刷题实践【java实现+详细注释】
一篇文章入门单链表+刷题实践【java实现+详细注释】
HelloDam
10685 2

热门文章

最新文章

  • 1
    Java社招面试中的高频考点：Callable、Future与FutureTask详解
  • 2
    接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
  • 3
    自研Java框架 Sunrays-Framework使用教程「博客之星」
  • 4
    【AI程序员】通义灵码 AI 程序员全面上线JAVA使用体验
  • 5
    微信小程序与Java后端实现微信授权登录功能
  • 6
    Java小抄 使用StopWatch输出执行耗时
  • 7
    java连接redis和基础操作命令
  • 8
    菜鸟之路Day06一一Java常用API
  • 9
    java引入本地 MultipartFile 实现多部分文件上传
  • 10
    Java线程调度揭秘：从算法到策略，让你面试稳赢！
  • 1
    Java HashMap详解及实现原理
    27
  • 2
    Java+机器学习基础：打造AI学习基础
    50
  • 3
    Java爬虫获取微店快递费用item_fee API接口数据实现
    34
  • 4
    Java爬虫获取微店店铺所有商品API接口设计与实现
    36
  • 5
    智慧产科一体化管理平台源码，基于Java，Vue，ElementUI技术开发，二开快捷
    33
  • 6
    Java社招面试题：一个线程运行时发生异常会怎样？
    50
  • 7
    java.time常用方法汇总
    17
  • 8
    Java容器及其常用方法汇总
    15
  • 9
    【AI程序员】通义灵码 AI 程序员全面上线JAVA使用体验
    198
  • 10
    尼恩一键开发环境： vagrant+java+springcloud+redis+zookeeper镜像下载(&制作详解)
    41

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 阿里云平台上进行Java程序的编译与运行
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
  • 搭建Java Web开发环境（Anolis OS）
  • RocketMQ中使用Java客户端发送消息和消费的应用
  • 部署基于Dragonwell的Java运行环境
    • 下一篇
    阿里云oss简介和如何对接使用