Skip to content

Instantly share code, notes, and snippets.

@coolcoolercool

coolcoolercool/src_一个链表是否有环_NodeTest.java

Created May 16, 2018 07:17
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save coolcoolercool/7b842da2ef5d5bda465567fb0a10fdc0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save coolcoolercool/7b842da2ef5d5bda465567fb0a10fdc0 to your computer and use it in GitHub Desktop.
Download ZIP
java面试的链表相关问题
Raw
src_一个链表是否有环_NodeTest.java
package 一个链表是否有环;
public class NodeTest
{
public static void main(String[] args)
{
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
head.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n3);//通过这里设置环，去掉//就是有环。
boolean x = hasCycle(head);
System.out.println(x);
}
static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
}
public static boolean hasCycle(Node head)
{
Node fast = head;
Node slow = head;
if(fast == null)
{
return false;
}
while(fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
{
return true;
}
}
return !(fast == null || fast.next == null);
}
}
Raw
src_不知道头指针的情况下删除指定结点_deleteNodeTest.java
package 不知道头指针的情况下删除指定结点;
//1.如果待删除的结点为链表尾结点，则无法删除，因为删除后无法使其前驱结点的next指针为置为null;
//2.如果待删除的结点不是尾结点，则可以通过交换这个结点与其后继结点的值，然后删除后继结点。
public class deleteNodeTest
{
public static void main(String[] args) {
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
head.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
Node h = head;
while(h != null)
{
System.out.print(h.getData() + " ");
h = h.next;
}
deleteNode(n3);
System.out.println("\n**************************");
while(head != null)
{
System.out.print(head.getData() + " ");
head = head.next;
}
}
static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public int getData() {
return data;
}
public Node getNext() {
return next;
}
}
private static boolean deleteNode(Node head)
{
//
if(head == null || head.next ==null)
return false;
int tmp = head.data;
head.data = head.next.data;
head.next.data = tmp;
head.next = head.next.next;
return true;
}
}
Raw
src_从尾到头输出单链表_ReversePrint.java
package 从尾到头输出单链表;
//利用递归实现链表倒序输出，已经是最佳方法之一，主要运用了栈的压栈和弹栈，先进后出的思想。
public class ReversePrint
{
public static void main(String[] args)
{
//创建链表
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = null;
ListNode head = n1;
while(head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("\n**************************");
printListReverse(n1);
}
static class ListNode
{
private int data;
private ListNode next;
ListNode(int data) {
//super();
this.data = data;
}
}
/**
* 方法一：通过栈反向打印链表
*/
/*public static void printListReverse(ListNode head){
Stack<ListNode> s = new Stack<ListNode>();
if(head == null){
return ;
}
while(head != null){
s.push(head);
head = head.next;
}
while(!s.empty()){
System.out.println(s.pop().data);
}
}*/
/**
* 方法二；通过递归方式
*/
public static void printListReverse(ListNode head)
{
if(head != null)
{
if(head.next != null)
{
ListNode nextListNode = head.next;
printListReverse(nextListNode);
}
//head.next为空 head不为空时开始打印head。
System.out.print(head.data + " ");
}
else
{
return;
}
}
}
Raw
src_如何判断两个链表是否相交_isIntersectTest.java
package 如何判断两个链表是否相交;
//
public class isIntersectTest
{
public static void main(String[] args)
{
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
Node n8 = new Node(8);
Node n9 = new Node(9);
Node n10 = new Node(10);
//链表一
head.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
//链表二
n6.setNext(n7);
n7.setNext(n8);
n8.setNext(n5);
//交点以后的部分
n5.setNext(n9);
n9.setNext(n10);
boolean x = isIntersect(head, n6);
System.out.println(x);
}
static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public int getData() {
return data;
}
public Node getNext() {
return next;
}
}
public static boolean isIntersect(Node head1, Node head2)
{
if(head1 == null || head2 == null)
return false;
Node tail1 = head1;
while(tail1.next != null)
{
tail1 = tail1.next;
}
Node tail2 = head2;
while(tail2.next != null)
{
tail2 = tail2.next;
}
return tail1 == tail2;
}
}
Raw
src_如何找到环的入口点_FindLoopPortTest.java
package 如何找到环的入口点;
public class FindLoopPortTest
{
public static void main(String[] args) {
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
head.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n2);
Node x = FindLoopPort(head);
System.out.println(x.data);
}
static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
}
public static Node FindLoopPort(Node head)
{
Node slow = head;
Node fast = head;
//找到快慢指针相遇点
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
break;
}
//错误检查，这是没有环的情况
if(fast == null || fast.next == null)
return null;
//现在，相遇点离环开始出的距离等于链表头到环开始的粗的距离，
//这样，我们再把慢指针放到链表头粗，快指针保持在相遇点，
//然后以同样的速度前进，再次相遇的点就是环的开始处。
slow = head;
while(slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
Raw
src_寻找单链表的中间结点_SearchMid.java
package 寻找单链表的中间结点;
//这里推荐使用的方法是使用快慢指针的方法实现。
public class SearchMid {
public static void main(String[] args) {
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
head.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
Node x = findMid(head);
System.out.println(x.data);
}
static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
}
private static Node findMid(Node head)
{
if(head == null || head.next ==null)
{
return head;
}
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next != null && fast.next.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
Raw
src_用java实现链表的反转_ReverseLinkedList.java
package 用java实现链表的反转;
//用递归反转的方法对链表进行反转操作。
public class ReverseLinkedList
{
public static void main(String[] args)
{
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
// 打印反转前的链表
Node h = head;
while (null != h) {
System.out.print(h.getData() + " ");
h = h.getNext();
}
// 调用反转方法
head = Reverse1(head);
System.out.println("\n**************************");
// 打印反转后的结果
while (null != head) {
System.out.print(head.getData() + " ");
head = head.getNext();
}
}
/**
* 递归，在反转当前节点之前先反转后续节点
*/
public static Node Reverse1(Node head) {
// head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
if (head == null || head.getNext() == null) {
return head;// 若为空链或者当前结点在尾结点，则直接还回
}
Node reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()
head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
head.setNext(null);// 前一结点的指针域令为null;
return reHead;// 反转后新链表的头结点
}
}
class Node {
private int Data;// 数据域
private Node Next;// 指针域
public Node(int Data) {
// super();
this.Data = Data;
}
public int getData() {
return Data;
}
public void setData(int Data) {
this.Data = Data;
}
public Node getNext() {
return Next;
}
public void setNext(Node Next) {
this.Next = Next;
}
}
Raw
src_用java实现链表的基本操作_LinkList.java
package 用java实现链表的基本操作;
public class LinkList<T>//泛型
{
private class Node//节点类
{
private T data;
private Node next;
public Node()//重载
{
}
public Node(T data,Node next)
{
this.data = data;
this.next = next;
}
}
private Node head;//指向链表头节点的引用变量
private Node tail;//指向链表尾节点的引用变量
int size;//链表中当前总节点数
//生成链表对象是一个空表
public LinkList()
{
head = null;
tail = null;
}
//生成链表对象时有一个头节点 （有参构造器）
public LinkList (T data)
{
head = new Node(data,null);//指定一个头节点的数据域值为data,不指向其他节点
tail = head;
size++;
}
//返回链表的长度
public int length()
{
return size;
}
//获取指定位置的元素
public T getElement(int index)
{
return findNodeByIndex(index).data;
}
//查找 指定索引位置的节点
public Node findNodeByIndex(int index)
{
if(index < 0 || index > size-1)
{
throw new IndexOutOfBoundsException("线性表索引越界");
}
Node current = head;//从头节点开始下移遍历
for (int i = 0;i < size & current.next!=null;i++,current = current.next)
{
if(i == index)
{
return current;
}
}
return null;
}
//查找 指定元素的位置(查找数据域存放的是element的节点位置)
public int findIndexByElement(T element)
{
Node current = head;//从第一个节点开始查找对比数据
for(int i=0; i<size&current.next!=null;i++,current=current.next)
{
if(current.data.equals(element))
return i;
}
return -1;
}
//插入 在指定位置插入一个元素
public void insert(int index,T element)
{
if(index < 0 || index > size)
{
throw new IndexOutOfBoundsException("线性表索引越界");
}
if(head == null)//如果链表为空，直接调用add方法
{
add(element);
}
else //链表不为空时
{
if(index==0)//在链表头插入
{
addAtHead(element);
}
else
{
Node prev = findNodeByIndex(index-1);//找到要插入位置的前一个节点
prev.next = new Node(element,prev.next);//插入后prev的next指向新节点，新节点的next指向原来prev的下一个节点
size++;
}
}
}
//插入 尾插法在每次在链表尾添加新节点
public void add(T element)
{
if(head==null)
{
head = new Node(element,null);
tail = head;
}
else
{
Node newNode = new Node(element,null);
tail.next = newNode;
tail = newNode;
}
size++;
}
//插入 头插法在链表头部加入新节点
public void addAtHead(T element)
{
//在头部插入新节点，就是让新节点的next指向原来的head,让新节点作为链表的头节点
head = new Node(element,head);
//newNode.next = head;
//head = newNode;
//如果插入之前是空链表
if(tail==null)
{
tail=head;
}
}
//删除指定位置的节点 返回删除节点中的元素值
public T delete (int index)
{
Node deleteNode = null;
if(index<0||index>size-1)
{
throw new IndexOutOfBoundsException("线性表索引越界");
}
if(index==0)//删除头节点
{
deleteNode = head;
head = head.next;
}
else
{
Node prev = findNodeByIndex(index-1);//获取要删除的节点的前一个节点
deleteNode = prev.next;//要删除的节点就是prev的next指向的节点
prev.next=deleteNode.next;//删除以后prev的next指向被删除节点之前所指向的next
deleteNode.next = null;
}
return deleteNode.data;
}
//删除 链表中最后一个元素
public T removeLast()
{
return delete(size-1);
}
//清除链表中所有的元素
public void clear()
{
head = null;
tail = null;
size = 0;
}
//判断链表是否为空
public boolean isEmpty()
{
return size==0;
}
public String toString()//链表的输出 重写toString方法
{
if(isEmpty())
{
return "[]";
}
else
{
StringBuilder sb = new StringBuilder("[");//使用StringBuilder类
for(Node current = head;current != null ; current = current.next)//从head开始遍历
{
sb.append(current.data.toString()+",");//把节点的数据拼接起来
}
int len = sb.length();
return sb.delete(len-1,len).append("]").toString();//把最后一个元素的，删除然后加上]
}
}
}
Raw
src_用java实现链表的基本操作_LinkListTest.java
package 用java实现链表的基本操作;
public class LinkListTest
{
public static void main(String[] args)
{
LinkList<String> list = new LinkList<String>();
list.add("aa");
list.add("bb");
list.add("cc");
System.out.println(list);
list.addAtHead("11");
list.insert(1,"22");
System.out.println(list);
list.delete(2);
System.out.println(list);
list.clear();
System.out.println(list);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment