天使的左手
- 浏览: 55589 次
- 性别:
- 来自: 杭州
-
最新评论
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import org.apache.commons.io.IOUtils;
//带头节点的单链表
public class LinkedList2<T>
{
public static void main(String[] args) throws CloneNotSupportedException
{
LinkedList2<Integer> list = new LinkedList2<Integer>(1, 2, 3, 4, 5);
// System.out.println(list.isEmpty());
// System.out.println(list.size());
// System.out.println(list.createEntry(1).next);
// System.out.println(list.getEntry(-1));
// System.out.println(list.getEntry(0));
// System.out.println(list.getEntry(2));
System.out.println(list);
// LinkedList2<Integer> n_list = (LinkedList2<Integer>) list.clone();
// System.out.println(n_list);
// LinkedList2.reverseListByIterator(n_list);
// LinkedList2.reverseListByRecursion(n_list);
// System.out.println(n_list);
// Entry<Integer> entry = LinkedList2.lastIndexOf(list, 2);
// Entry<Integer> entry = LinkedList2.lastIndexOfByArray(list, 5);
// Entry<Integer> entry = LinkedList2.getMiddleEntry(list);
// System.out.println(entry == null ? "not found" : entry.element);
// LinkedList2.reversePrintListByStack(list);
// LinkedList2.reversePrintListByRecursion(list);
// LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 2, 2, 5);
// LinkedList2<Integer> list2 = new LinkedList2<Integer>(2, 3, 3, 3, 4);
// System.out.println(list1);
// System.out.println(list2);
// LinkedList2<Integer> n_list = LinkedList2.mergeList(list1, list2);
// System.out.println(n_list);
// LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3);
// Entry<Integer> lastEntry = list1.getEntry(list1.size() - 1);
// Entry<Integer> firstEntry = list1.getEntry(0);
// lastEntry.next = firstEntry;
// System.out.println(LinkedList2.hasLoop(list1));
// Entry<Integer> entry = LinkedList2.getFirstEnterLoopEntry(list1);
// Entry<Integer> entry = LinkedList2.getFirstEnterLoopEntry2(list1);
// System.out.println(entry == null ? "no loop" : entry.element);
// LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3, 4);
// LinkedList2<Integer> list2 = new LinkedList2<Integer>(11, 22, 33,
// 44);
// // list2.getEntry(2).setNext(list1.getEntry(1));
// list2.getEntry(3).setNext(list1.getEntry(3));
// System.out.println(list1);
// System.out.println(list2);
// System.out.println(LinkedList2.isIntersect(list1, list2));
// System.out.println(LinkedList2.isIntersect2(list1, list2));
// System.out.println(LinkedList2.isIntersect3(list1, list2));
//
// Entry<Integer> entry = LinkedList2.getFirstIntersectEntry(list1,
// list2);
// System.out.println(entry == null ? "not found" : entry.element);
// LinkedList2.deleteEntry(list, list.getEntry(4));
// System.out.println(list);
LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3, 4, 2, 3, 4, 5, 1);
System.out.println(list1);
LinkedList2.deleteDuplicateEntries(list1);
System.out.println(list1);
}
//头指针
private Entry<T> head;
public LinkedList2()
{
//初始化一个头节点，让头指针指向这个头节点
head = new Entry<T>(null);
}
public LinkedList2(T... elements)
{
this();
//尾指针,一开始指向头节点
Entry<T> tail = head;
for (T element : elements)
{
//实例化一个新的节点,next为null
Entry<T> newEntry = new Entry<T>(element, null);
//让尾指针的next指向新的节点
tail.next = newEntry;
//尾指针后移一位指向新的节点
tail = newEntry;
}
}
public void setHead(Entry<T> head)
{
this.head = head;
}
public boolean isEmpty()
{
//头节点的next为空，则整个链表为空
return head.next == null;
}
// 1. 求单链表中结点的个数
public int size()
{
if (isEmpty())
return 0;
Entry<T> curEntry = head.next;
int c = 0;
while (curEntry != null)
{
c++;
curEntry = curEntry.next;
}
return c;
}
// 2. 将单链表反转: reverseList（遍历）
public static <T> void reverseListByIterator(LinkedList2<T> list)
{
Entry<T> curEntry = list.head.next; //第一个节点
Entry<T> nextEntry = null; //第二个节点
Entry<T> nextnextEntry = null; //第三个节点
//如果当前链表没有节点或者只有一个节点，直接返回
if (curEntry == null || curEntry.next == null)
return;
//循环前:
// head -> first -> second -> third .. -> null
// [cur] [next] [nextnext]
//一轮循环结束：
// head -> second -> first -> third .. -> null
// [next] [cur] [nextnext]
// ................
//如果当前节点是最后一个节点，退出循环
while (curEntry.next != null)
{
//当前节点的下一个节点
nextEntry = curEntry.next;
//当前节点的下下个节点
nextnextEntry = nextEntry.next;
//让第二个节点的next指向第一个节点
nextEntry.next = list.head.next;
//让头节点的next指向第二个节点
list.head.next = nextEntry;
//让第一个节点的next指向第三个节点
curEntry.next = nextnextEntry;
}
}
// 2. 将单链表反转: reverseListRec（递归）
public static <T> void reverseListByRecursion(LinkedList2<T> list)
{
//同上，链表中没有节点或者只有一个节点，直接返回
if (list.head.next == null || list.head.next.next == null)
return;
list.head.next = reverseList(list.head.next);
}
private static <T> Entry<T> reverseList(Entry<T> head)
{
//比如有链表 1 -> 2 -> 3 -> 4 -> null
//最后一轮的head是4 -> null,直接返回这个head
//倒数第二轮,head是3 -> 4 - > null,将最后一轮返回的head赋给newHead
//newHead -> 4 -> null ↓ - - ↑
//执行head.next.next = head 得到newHead -> 4 - > 3 出现了环
//最后执行head.next = null将环打破, 得到newHead -> 4 - > 3 -> null
//.........
//如果是最后一个节点，直接返回
if (head.next == null)
return head;
//倒数第二轮递归时，得到最后一轮返回的节点（最后一个节点），作为新链表的第一个节点
Entry<T> newHead = reverseList(head.next);
//第二个节点的next指向第一个节点
head.next.next = head;
//第一个节点的next置为null
head.next = null;
return newHead;
}
// 3. 查找单链表中的倒数第K个结点（k > 0）
public static <T> Entry<T> lastIndexOf(LinkedList2<T> list, int n)
{
if (n <= 0)
throw new IllegalArgumentException("The number should be greater than zero");
//获得第n个节点，赋值给first
Entry<T> first = list.getEntry(n - 1);
//second指向头节点
Entry<T> second = list.head;
//first和second以相同的频率前进,直到最后一个节点
while (first != null)
{
first = first.next;
second = second.next;
}
//此时second指针指向的节点就是倒数第n个节点
return second;
}
// 3. 查找单链表中的倒数第K个结点（k > 0）,数组实现
@SuppressWarnings("unchecked")
public static <T> Entry<T> lastIndexOfByArray(LinkedList2<T> list, int n)
{
if (n <= 0)
throw new IllegalArgumentException("The number should be greater than zero");
Object[] entries = new Object[n];
int c = 0, index = 0;
Entry<T> curEntry = list.head.next;
while (curEntry != null)
{
entries[index] = curEntry;
index = (index + 1) % n; //索引值永远不会超过n
c++;
curEntry = curEntry.next;
}
if (entries[index] == null)
throw new IllegalStateException("Less than " + n + " elements, current is " + c);
return Entry.class.cast(entries[index]);
}
// 4. 查找单链表的中间结点
public static <T> Entry<T> getMiddleEntry(LinkedList2<T> list)
{
if (list.isEmpty())
return null;
Entry<T> first = list.head;
Entry<T> second = list.head;
//first每次向前走两步，second每次走一步，当first到链表结尾，second指针指向的节点就是中间节点
while (first != null && first.next != null)
{
first = first.next.next;
second = second.next;
}
return second;
}
// 5. 从尾到头打印单链表,通过栈实现
public static <T> void reversePrintListByStack(LinkedList2<T> list)
{
java.util.LinkedList<T> stack = new java.util.LinkedList<T>();
Entry<T> curEntry = list.head;
while (curEntry.next != null)
{
stack.push(curEntry.next.element);
curEntry = curEntry.next;
}
String result = "[";
while (!stack.isEmpty())
{
result += stack.pop();
result += ", ";
}
if (result.length() > 1)
result = result.substring(0, result.length() - 2);
result += "]";
System.out.println(result);
}
// 5. 从尾到头打印单链表（递归）
public static <T> void reversePrintListByRecursion(LinkedList2<T> list)
{
String result = reversePrint(list.head);
if (result.length() > 0)
result = result.substring(0, result.length() - 2);
System.out.println("[" + result + "]");
}
private static <T> String reversePrint(Entry<T> entry)
{
if (entry.next == null)
return "";
String result = reversePrint(entry.next);
result += entry.next.element + ", ";
return result;
}
// 6. 已知两个单链表list1和list2各自有序，把它们合并成一个链表依然有序
@SuppressWarnings("unchecked")
public static <T> LinkedList2<T> mergeList(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
Entry<T> newHead = new Entry<T>(null);
Entry<T> preEntry = newHead;
while (curEntry1.next != null && curEntry2.next != null)
{
//如果entry1的element小于entry2的element，则把entry1加到新的链表中去
if (((Comparable) curEntry1.next.element).compareTo(curEntry2.next.element) < 0)
{
//每次重新实例化一个节点对象
preEntry.next = new Entry<T>(curEntry1.next.element, null);
curEntry1 = curEntry1.next;
}
else
{
//否则，把entry2加到新链表中去
preEntry.next = new Entry<T>(curEntry2.next.element, null);
curEntry2 = curEntry2.next;
}
preEntry = preEntry.next;
}
//将list1链表剩余的entry加到新的链表中去
while (curEntry1.next != null)
{
preEntry.next = new Entry<T>(curEntry1.next.element);
curEntry1 = curEntry1.next;
preEntry = preEntry.next;
}
//将list2链表剩余的entry加到新的链表中去
while (curEntry2.next != null)
{
preEntry.next = new Entry<T>(curEntry2.next.element);
curEntry2 = curEntry2.next;
preEntry = preEntry.next;
}
//返回一个全新的链表
LinkedList2<T> result = new LinkedList2<T>();
result.setHead(newHead);
return result;
}
// 7. 判断一个单链表中是否有环
public static <T> boolean hasLoop(LinkedList2<T> list)
{
Entry<T> first = list.head;
Entry<T> second = list.head;
//first每次往前走两步，second每次走一步，当在某个节点first和second相等了，说明这个链表存在环
while (first != null && first.next != null)
{
first = first.next.next;
second = second.next;
if (first == second)
return true;
}
return false;
}
// 8. 已知一个单链表中存在环，求进入环中的第一个节点
public static <T> Entry<T> getFirstEnterLoopEntry(LinkedList2<T> list)
{
Entry<T> first = list.head;
Entry<T> second = list.head;
//first每次往前走两步，second每次走一步，当在某个节点first和second相等了，说明有环，
//此时，让first从这个相交的节点开始，second从头节点开始，每次往前走一步，
//当first和second再次相同, 这个节点就是进入环的第一个节点
while (first != null && first.next != null)
{
first = first.next.next;
second = second.next;
if (first == second)
break;
}
if (first == null || first.next == null)
return null;
second = list.head;
while (first != second)
{
first = first.next;
second = second.next;
}
return first;
}
// 8. 已知一个单链表中存在环，求进入环中的第一个节点 HashMap实现
public static <T> Entry<T> getFirstEnterLoopEntry2(LinkedList2<T> list)
{
HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
Entry<T> curEntry = list.head;
//每次将节点放到map之前，检查一下map中是否已经存在这个节点了，如果存在，那这个节点就是
//进入环中的第一个节点了
while (curEntry != null)
{
if (storage.get(curEntry) == Boolean.TRUE)
return curEntry;
else
{
storage.put(curEntry, Boolean.TRUE);
curEntry = curEntry.next;
}
}
return null;
}
// 9. 判断两个单链表是否相交 HashMap实现
public static <T> boolean isIntersect(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
//将list1中的节点都存储到map中去
while (curEntry1.next != null)
{
storage.put(curEntry1.next, Boolean.TRUE);
curEntry1 = curEntry1.next;
}
//遍历list2中的节点，跟map中已存在的节点比较，如果找到相同的节点，
//这个节点就是两个链表的交点
while (curEntry2.next != null)
{
if (storage.get(curEntry2.next) == Boolean.TRUE)
return true;
curEntry2 = curEntry2.next;
}
return false;
}
// 9. 判断两个单链表是否相交 如果相交 让第一个链表的next指向第二个链表的头指针，可以构成一个环
public static <T> boolean isIntersect2(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
while (curEntry1.next != null)
curEntry1 = curEntry1.next;
curEntry1.next = list2.head;
boolean exist = false;
while (curEntry2.next != null)
{
if (curEntry2.next == list2.head)
{
exist = true;
break;
}
curEntry2 = curEntry2.next;
}
//将list1的next置为null，一定不要忘记
curEntry1.next = null;
return exist;
}
// 9. 判断两个单链表是否相交 如果相交 最后一个节点一定相等
public static <T> boolean isIntersect3(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
while (curEntry1.next != null)
curEntry1 = curEntry1.next;
while (curEntry2.next != null)
curEntry2 = curEntry2.next;
if (curEntry1 == curEntry2)
return true;
return false;
}
// 10. 求两个单链表相交的第一个节点
public static <T> Entry<T> getFirstIntersectEntry(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
int m = 0, n = 0;
//得到第一个链表的长度
//m = list1.size();
while (curEntry1.next != null)
{
m++;
curEntry1 = curEntry1.next;
}
//得到第二个链表的长度
//n = list2.size()
while (curEntry2.next != null)
{
n++;
curEntry2 = curEntry2.next;
}
curEntry1 = list1.head;
curEntry2 = list2.head;
int c;
if (m > n)
{
c = m - n;
while (c != 0)
{
curEntry1 = curEntry1.next;
c--;
}
}
else
{
c = n - m;
while (c != 0)
{
curEntry2 = curEntry2.next;
c--;
}
}
//让list1和list2从同一个起点开始遍历
while (curEntry1 != null)
{
curEntry1 = curEntry1.next;
curEntry2 = curEntry2.next;
//这个相同的entry就是交点
if (curEntry1 == curEntry2)
return curEntry1;
}
return null;
}
// 11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted: delete
public static <T> void deleteEntry(LinkedList2<T> list, Entry<T> entry)
{
if (entry == null)
return;
//当前节点不是最后一个节点
if (entry.next != null)
{
entry.element = entry.next.element;
entry.next = entry.next.next;
}
else
{
//最后一个节点，且该链表仅有一个元素
if (list.head.next == entry)
list.head.next = null;
else
{
//链表包含多个元素
Entry<T> preEntry = list.head;
while (preEntry.next != null && preEntry.next != entry)
{
preEntry = preEntry.next;
}
if (preEntry.next == null)
throw new IllegalStateException("No element found " + entry);
preEntry.next = preEntry.next.next;
}
}
}
// 12.删除单链表中重复的元素
public static <T> void deleteDuplicateEntries(LinkedList2<T> list)
{
Set<T> entries = new HashSet<T>();
Entry<T> curEntry = list.head;
while (curEntry.next != null)
{
if (entries.contains(curEntry.next.element))
curEntry.next = curEntry.next.next;
else
{
entries.add(curEntry.next.element);
curEntry = curEntry.next;
}
}
}
@SuppressWarnings("unchecked")
@Override
public Object clone() throws CloneNotSupportedException
{
try
{
ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);
try
{
oos.writeObject(head);
oos.flush();
ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray()));
try
{
LinkedList2<T> result = new LinkedList2<T>();
result.setHead(Entry.class.cast(ois.readObject()));
return result;
}
finally
{
IOUtils.closeQuietly(ois);
}
}
finally
{
IOUtils.closeQuietly(oos);
}
}
catch (Exception e)
{
e.printStackTrace();
return super.clone();
}
}
public Entry<T> createEntry(T element)
{
return new Entry<T>(element);
}
public Entry<T> getEntry(int index)
{
if (index < 0)
throw new IllegalArgumentException("index should be a positive number or zero");
int c = 0;
Entry<T> curEntry = head.next;
while (curEntry != null && c < index)
{
curEntry = curEntry.next;
c++;
}
if (curEntry == null)
throw new IllegalStateException("Less than " + (index + 1) + " elements, current is " + c);
return curEntry;
}
@Override
public String toString()
{
String result = "[";
Entry<T> curEntry = head.next;
while (curEntry != null)
{
result += curEntry.element;
curEntry = curEntry.next;
if (curEntry != null)
result += ", ";
}
return result + "]";
}
public static class Entry<T> implements Serializable
{
private static final long serialVersionUID = 1L;
T element;
Entry<T> next;
public void setElement(T element)
{
this.element = element;
}
public T getElement()
{
return element;
}
public void setNext(Entry<T> next)
{
this.next = next;
}
Entry(T element)
{
this(element, null);
}
Entry(T element, Entry<T> next)
{
this.element = element;
this.next = next;
}
@Override
public String toString()
{
return String.valueOf(element);
}
}
}
分享到：
发表评论
-
redis安装(windows.exe)
2014-05-21 22:54 738https://github.com/rgl/redis ... -
rabbitMQ安装(windows下)
2014-05-21 22:41 653进入项目下载主页面http://www.rabbitmq.co ... -
实现单线程的断点下载
2014-04-16 09:43 843/** * 实现单线程的断点下载 */ publ ... -
实现一个简易的http模拟器
2014-04-15 15:20 1798/** * http模拟器 * 模拟发送http请求和 ... -
xml学习鉴定
2014-04-09 23:33 841实现招生录取系统中的 ... -
xml学习
2014-04-08 22:47 1473XML：Extensible Markup Langu ... -
HTTP断点续传
2014-03-31 22:13 793http://fenglingcorp.iteye.com/b ... -
java多线程-线程状态转换
2014-03-01 09:20 7961. 新建(new)：新创建了一个线程对象。 2. 可 ... -
apt处理自定义annotation
2014-02-19 23:20 1022package annotations; import ... -
跳过UTF-8的BOM
2014-02-14 12:19 1503/** version: 1.1 / 2007-01-25 ... -
java reference
2014-02-09 00:36 676import java.lang.ref.PhantomR ... -
不带头结点的单链表面试汇总
2014-01-24 13:47 1496import java.io.ByteArrayInputSt ... -
单链表面试题之-链表反转
2014-01-15 22:43 1101单链表反转 -------------------- ... -
java单链表-带头结点和不带头结点单链表的简单实现
2014-01-14 23:41 4931带头结点的单链表实现 public class LinkedL ... -
ClassLoader
2013-11-08 15:57 908public class ClassLoaderTest { ... -
URL和URI
2013-11-08 13:48 513private static void getData ... -
i++和++i
2013-11-06 15:26 524// i = i++ 计算过程 // temp = i; ... -
java 继承 多态
2013-11-06 15:19 802/** 运行结果： A's constructor co ... -
sealing violation
2013-11-03 16:10 3140一般以下两种情况会触发sealing安全异常 1）当被密封（s ... -
hashmap分析
2013-10-30 15:20 693/** hashmap底层维护着一个entry数组,每 ...
相关推荐
### 带头结点单链表的基本操作详解 #### 引言 单链表是数据结构中的一个重要概念，尤其在计算机科学与编程领域中应用广泛。带头结点的单链表是在链表的最前端添加一个额外的节点，这个节点不存储实际的数据，其作用...
使用C++面向对象的方法实现带头结点的单链表的插入,删除等基本操作.
利用带头结点的单链表实现两个集合的并、交、差运算 本文档的主要内容是使用带头结点的单链表实现两个集合的并、交、差运算。该文档共分为八个部分，分别是题目重述、题目功能描述、概要设计图、程序源代码及注释、...
/*带头结点头文件 hlinklist.h*/ #include <stdio.h> typedef int datatype; typedef struct link_node { datatype data; struct link_node *next; }node; /*初始化链表*/ node *init() { node *head; head=...
不带头结点，不带头结点，不带头结点！ 实现单链表及其一些基本操作函数（不带头结点） 1.头文件包含 2.宏定义及节点类型描述 3.初始化、判断是否为空 4.指定位置插入操作 5.在p节点后插入元素e 6.在p节点前...
不带头结点单链表.cpp
不带头结点的单链表是指链表的第一个节点没有专门的头结点，而是直接由数据节点开始。这种链表的处理在某些特定场景下更方便，但需要特别注意对链表起始位置的处理。下面将详细解释如何用C++实现不带头结点单链表的...
本主题将深入探讨一种常见的线性数据结构——带头结点的单链表，以及其相关的定义与基本操作的源代码实现。 单链表是一种动态数据结构，其中每个元素（称为节点）包含两部分：数据域，存储实际的数据；指针域，指向...
总之，不带头结点的单链表是一种简洁的数据结构实现，尽管在某些操作上可能不如带头结点的链表方便，但在特定情况下，它可以提供有效的解决方案。理解其工作原理和如何用C++进行操作对于提升编程技能和优化算法性能...
本压缩包“带头结点单链表.zip”提供的内容着重于如何在实际编程中实现带有头结点的单链表。 首先，我们需要理解单链表的基本概念。单链表是由一系列节点构成的，每个节点包含两部分：数据域和指针域。数据域用于...
给定一个不带头结点的单链表，写出将链表倒置的算法
使用尾插法建立一个带头结点的单链表，然后输出结果
### 带头结点的单链表存储结构与基本操作 #### 一、概述 在计算机科学领域，数据结构是研究数据组织方式及其运算的重要工具。其中，单链表是一种常见的线性表存储结构，它通过一组节点来表示一个序列，每个节点...
当我们谈论“带头结点”的单链表时，意味着在链表的第一个元素前还有一个特殊的节点，称为头结点。头结点不包含实际数据，而是用作链表的起点，并简化了对链表的操作。 在C语言中，实现带头结点的单链表涉及以下几...
将带头结点的单链表实现线性表的功能
带头结点的单链表，将其翻转，输出。typedef struct lnode { int data; struct lnode *next;/*指针域*/ } lnode,*linklist; /**linklist表示struct lnode类型的指针；lnode是别名*/
最近在学数据结构，自己写的很简单的小程序，积跬步、至千里。
在带头结点的单链表上实现线性操作（返回表长）
1.若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求： （1）给定一个城市名，返回其位置坐标。 （2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。
带头结点的单链表的建立，按值查找，计算表长，及其输出单链表中的数据