开发者社区> shy丶gril> 正文

java单链表常用操作

简介:
+关注继续查看

总结提高,与君共勉

概述、

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

【链表个数】

【反转链表-循环】

【反转链表-递归】

【查找链表倒数第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算法基础 - 单链表详解(文末有配套视频)
咳咳,我是小白,没错,主线剧情又回来了。现在我遇到麻烦了,老板要我设计一个类,可以用来保存多个客户的资料。
20 0
【Java基础】 建立一个单链表(增删查改)
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
22 0
《Java数据结构基础》单链表的手动实现
《Java数据结构基础》单链表的手动实现
15 0
【Java数据结构】实现单链表
【Java数据结构】实现单链表
23 0
Java单链表的应用实例
Java单链表的应用实例
24 0
Java数据结构之单链表(配图详解,简单易懂)
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的,看着这段文字抽象不,生硬不(本笔记主要介绍单向不带头节点非循环链表)
42 0
java语言实现单链表---不含头结点
java实现单链表—含头结点,且该篇文章与另一篇含头结点的实现单链表的文章第一部分均是重复的,若看可忽略,说到这里必须要写下含不含头结点的区别,带有头结点是为了更好的实现单链表的功能,带有头结实现的insert、remove等方法相比于不带头结点的单链表会更简洁一些,此外,学习不带头结点的和带有头结点的单链表是没有区别的。
23 0
java语言实现单链表--含头结点
线性表是我们最常用的一种数据结构,线性表包含顺序表和链表,顺序表典型应用就是我们常用的ArrayList,链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结单链表的实现以及使用并且对比单链表与顺序表的优缺点,确定其使用功能场景。
37 0
单链表的基本操作(Java实现)
单链表的基本操作(Java实现)
84 0
通用版!完整代码,单链表SingleLinkedList增删改查,反转,逆序,有效数据等Java实现
通用版!完整代码,单链表SingleLinkedList增删改查,反转,逆序,有效数据等Java实现
37 0
+关注
shy丶gril
文章
问答
视频
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
JAVA开发手册1.5.0
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
相关实验场景
更多