首页 / JAVA / 用java实现单链表的问题汇总
用java实现单链表的问题汇总
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了用java实现单链表的问题汇总，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4482字，纯文字阅读大概需要7分钟。
内容图文
单链表的每个结点都包含有值，还包含链接下一结点的引用字段。链表将所有结点按顺序链接组织起来。以上为链表的基本定义，最近写了单链表的一些实现，也进行了一些思考，当然我的思考可能有所遗漏或者不对，写出来的代码健壮性可能不太好，如果有错误或更好的方法欢迎大家指正。先总结一下单链表，之后找个时间再总结一下双链表。
首先链表定义如下：
1
public
class
Node {
2
3 Node next = null;
4int val;
5public Node(int x) {
6 val = x;
7 }
8 }
新建一个类，实现关于单链表的一些问题，首先定义了头变量
Node head = null;
实现链表的增加：关于链表的增加，其实可以汇总成一个方法，但是这里分为了从头、尾、和中段插入结点
//
链表头部插入新节点
public
void addFirst(int value) {
Node node = new Node(value);
if(head != null) {
node.next = head;
head = node;
}
head = node;
}
//链表尾部插入新节点publicvoid addLast(int value) {
/*Node node = new Node(value);
Node cur = head;
if (head == null) {
cur = node;
return;
}
while(cur != null) {
cur = cur.next;
}
cur.next = node;*/
add(length(), value);
}
//链表的长度publicint length() {
int length = 0;
Node cur = head;
while(cur != null) {
length++;
cur = cur.next;
}
return length;
}
//链表中间插入publicvoid add(int index,int value) {
Node cur = head;
if (index < 0 || index > length()) {
thrownew IllegalArgumentException("违法操作，索引不存在");
}
if (index == 0) {
addFirst(value);
}else {
for (int i = 0; i < index-1 ;i++) {
cur = cur.next;
}
Node node = new Node(value);
node.next = cur.next;
cur.next = node;
}
}
链表实现打印的功能，实际就是对链表进行遍历：
//
链表打印
public
void
printList() {
Node cur = head;
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
}
链表的删除我写作了一个方法，根据索引去对某个结点进行删除操作
//
链表删除
public
void delete(int index) {
Node pre = head;
if (index < 0 || index > length()) {
thrownew IllegalArgumentException("违法操作，索引不存在");
}
if (index == 0) {
if(head != null) {
head = head.next;
return;
}else {
System.out.println("首节点为空");
}
}
else {
for(int i = 0; i < index -1; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
}
}
链表根据索引进行某个结点的查询，并返回某个结点的值
//
链表根据索引查询返回值
public
int findNode(int index) {
Node pre = head;
if (index < 0 || index > length()) {
thrownew IllegalArgumentException("违法操作，索引不存在");
}else {
if (head == null) {
return 0;
}
else {
for (int i = 0 ;i < index ; i++) {
pre = pre.next;
}
}
}
return pre.val;
}
查找倒数第n个结点，这里的思路是在单链表中定义两个指向头部的结点，比如a和b，让a结点先走n步，然后a、b同时开始遍历结点，当a走到为null时，b恰好走到倒数第n个节点。以下的index为倒数目标结点的索引值，两者之间的关系是index=n-1。
public
int findRevNode(int index) {
Node before = head;
Node behind = head;
if (index < 0 || index > length()) {
thrownew IllegalArgumentException("违法操作，索引不存在");
} else {
if (head == null) {
return 0;
}else {
for(int i = 0;i < index;i++) {
before = before.next;
}
while(before.next != null) {
before = before.next;
behind = behind.next;
}
}
}
return behind.val;
}
反转链表的思路，定义三个结点，分别为前中后，后结点指向中结点，最后前结点遍历到最后一个结点时，赋予为头结点
//
反转链表
public
void
reverseLink() {
Node curNode = head;//头结点
Node preNode = null;//前一个结点while(curNode != null) {
Node nextNode = curNode.next;//保留下一个节点
curNode.next = preNode;//指针反转
preNode = curNode;//前结点后移
curNode = nextNode;//当前结点后移 }
head = preNode;
}
链表有环，类比一快一慢的人在环形跑道跑步，快的人总会和慢的人相遇。以及入环点问题。
//
链表有环
public
boolean
hasCycle(Node head) {
if (head.next == null) {
returnfalse;
}
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
returntrue;
}
}
returnfalse;
}
//链表入环点public Node findPort(Node head) {
//先判断是否有环
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) {
returnnull;
}
//从链表头到环入口点等于(n - 1)循环内环 + 相遇点到环入口点，
//在链表头和环入口点分别设置一个指针，
//同时出发，每次各走一步，它们必定会相遇，且第一次相遇的点就是环入口点。
slow = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
两个链表的相交和相交点，可以类比成y横放的形状，必有相交点，且后面的结点相同
//
两个链表是否相交
public
boolean
point(Node head1,Node head2) {
if (head1 == null || head2== null) {
returnfalse;
}
while(head1.next != null) {
head1 = head1.next;
}
while (head2.next != null) {
head2 = head2.next;
}
if(head1 == head2) {
returntrue;
}
else {
returnfalse;
}
}
//相交链表的相交点public Node findPoint(Node head1,Node head2) {
if(head1 == null || head2 == null) {
returnnull;
}
Node p1 = head1;
Node p2 = head2;
int len1 = 0;
int len2 = 0;
int diff = 0;
while(p1.next != null) {
p1 = p1.next;
len1++;
}
while(p2.next != null) {
p2 = p2.next;
len2++;
}
if (p1 != p2) {
returnnull;
}
diff = Math.abs(len1-len2);
if(len1 > len2) {
p1 = head1;
p2 = head2;
}else {
p1 = head2;
p2 = head1;
}
for (int i = 0; i < diff; i++) {
p1 = p1.next;
}
while(p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
以上为单链表的练习与总结。
原文：https://www.cnblogs.com/mosachan/p/11909394.html
内容总结
以上是互联网集市为您收集整理的用java实现单链表的问题汇总全部内容，希望文章能够帮你解决用java实现单链表的问题汇总所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。