单链表的每个结点都包含有值,还包含链接下一结点的引用字段。链表将所有结点按顺序链接组织起来。以上为链表的基本定义,最近写了单链表的一些实现,也进行了一些思考,当然我的思考可能有所遗漏或者不对,写出来的代码健壮性可能不太好,如果有错误或更好的方法欢迎大家指正。先总结一下单链表,之后找个时间再总结一下双链表。
首先链表定义如下:
1 public class Node { 2 3 Node next = null; 4 int val; 5 public 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; } //链表尾部插入新节点 public void 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); } //链表的长度 public int length() { int length = 0; Node cur = head; while(cur != null) { length++; cur = cur.next; } return length; } //链表中间插入 public void add(int index,int value) { Node cur = head; if (index < 0 || index > length()) { throw new 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()) { throw new 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()) { throw new 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()) { throw new 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) { return false; } Node fast = head; Node slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return true; } } return false; } //链表入环点 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) { return null; } //从链表头到环入口点等于(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) { return false; } while(head1.next != null) { head1 = head1.next; } while (head2.next != null) { head2 = head2.next; } if(head1 == head2) { return true; } else { return false; } } //相交链表的相交点 public Node findPoint(Node head1,Node head2) { if(head1 == null || head2 == null) { return null; } 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) { return null; } 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