今天练习单向链表的一些操作，在过程中遇到了 一些问题，一直没摸着头脑
同时创建了两个单向链表的实例，并加入相关的数据，前面输出都是正常输出数据的，在调试的过程中发现链表实例list的数据混乱了。也没有进行其他的操作，头大
控制台输出：
list:当前链表长度：6
Student(no=1, age=22, name=lucy)
Student(no=2, age=29, name=roan)
Student(no=3, age=18, name=king)
Student(no=4, age=22, name=smith)
Student(no=5, age=16, name=andy)
Student(no=6, age=16, name=jack)
singleLinkedList:当前链表长度：3
Student(no=2, age=29, name=roan)
Student(no=4, age=22, name=smith)
Student(no=7, age=16, name=json)
list:当前链表长度：6
Student(no=1, age=22, name=lucy)
Student(no=2, age=29, name=roan)
Student(no=4, age=22, name=smith)
Student(no=7, age=16, name=json)
代码：
public class SingleLinkedList01 {
public static void main(String[] args) {
Student lucy = new Student(1, 22, "lucy");
Student roan = new Student(2, 29, "roan");
Student king = new Student(3, 18, "king");
Student smith = new Student(4, 22, "smith");
Student andy = new Student(5, 16, "andy");
Student jack = new Student(6, 16, "jack");
Student json = new Student(7, 16, "json");
Node<Student> node = new Node<>(lucy.getNo(),lucy);
Node<Student> roanNode = new Node<>(roan.getNo(), roan);
Node<Student> kingNode = new Node<>(king.getNo(), king);
Node<Student> smithNode = new Node<>(smith.getNo(), smith);
Node<Student> andyNode = new Node<>(andy.getNo(), andy);
Node<Student> jackNode = new Node<>(jack.getNo(), jack);
Node<Student> jsonNode = new Node<>(json.getNo(), json);
SingleLinkedList<Student> list = new SingleLinkedList<>();
list.addOrderByNo(node);
list.addOrderByNo(roanNode);
list.addOrderByNo(kingNode);
list.addOrderByNo(smithNode);
list.addOrderByNo(andyNode);
list.addOrderByNo(jackNode);
System.out.print("list:");
list.show();
SingleLinkedList<Student> singleLinkedList = new SingleLinkedList<>();
singleLinkedList.addOrderByNo(roanNode);
singleLinkedList.addOrderByNo(smithNode);
singleLinkedList.addOrderByNo(jsonNode);
System.out.print("singleLinkedList:");
singleLinkedList.show();
/*System.out.println("两个链表共同值：");
List<Node<Student>> nodes = list.mergeSingleLinkedList(singleLinkedList);
if (nodes != null && nodes.size() >0) {
for (Node<Student> studentNode : nodes) {
System.out.println(studentNode.getData());
}
}*/
System.out.print("list:");
list.show();
}
}
/**
* 单向链表
*/
class SingleLinkedList<T>{
/**
* 链表头结点 first
*/
private Node<T> first = new Node<>(0, null);
/**
* 单向链表的长度
*/
private int size = 0;
public int getSize(){
return size;
}
/**
* 新增节点 无需新增
* @param node 节点
*/
public void add(Node<T> node) {
Node<T> temp = first;
while (temp.getNext() != null) {
temp = temp.getNext();
}
size++;
temp.setNext(node);
}
/**
* 新增节点 有序新增，按照节点的no号从小到大排列
* @param node 新增节点
*/
public void addOrderByNo(Node<T> node) {
Node<T> cur = first;
while (true) {
if (cur.getNext() == null) {
size++;
break;
}
//当前节点指向下一个节点的index大于正在插入的节点index，结束循环
if (cur.getNext().getIndex() > node.getIndex()){
size++;
break;
}
//如果插入的index存在，结束循环，值替换
if (cur.getNext().getIndex() == node.getIndex()) {
break;
}
cur = cur.getNext();
}
node.setNext(cur.getNext());
cur.setNext(node);
}
/**
* 获取头节点
* @return firstNode
*/
public Node<T> getFirst(){
Node<T> res = null;
if (first.getNext() == null) {
System.err.println("链表为null");
}else{
res = first.getNext();
first.setNext(res.getNext());
}
size--;
return res;
}
public Node<T> getLast() {
Node<T> res = null;
if (first.getNext() == null) {
System.err.println("链表为null");
}else{
Node<T> cur = first.getNext();
while (cur.getNext().getNext() != null) {
cur = cur.getNext();
}
size--;
res = cur.getNext();
cur.setNext(null);
}
return res;
}
public void inversion() {
if (first.getNext() == null) {
System.err.println("链表为null");
}else{
Node<T> cur = first.getNext();
Node<T> inversion = new Node<>(-1, null);
Node<T> next;
while (cur != null) {
next = cur.getNext();
cur.setNext(inversion.getNext());
inversion.setNext(cur);
cur = next;
}
first.setNext(inversion.getNext());
}
}
/**
* 链表反转，利用栈Stack的特性：先进后出
*/
public void inversionByStack() {
Stack<Node<T>> inversion = new Stack<>();
if (first.getNext() == null) {
System.err.println("链表为null");
}else{
Node<T> cur =first.getNext();
while (cur != null) {
inversion.add(cur);
cur = cur.getNext();
}
while (!inversion.isEmpty()) {
System.out.println(inversion.pop().getData());
}
}
}
/**
* 合并链表，得到共同部分
*
* @param singleLinkedList
*/
public List<Node<T>> mergeSingleLinkedList(SingleLinkedList<T> singleLinkedList) {
List<Node<T>> result = new ArrayList<>();
//两链表不能为null
if (singleLinkedList.first.getNext() == null || this.first.getNext() == null) {
return result;
}
Node<T> thisCur = this.first.getNext();
Node<T> nodeCur = singleLinkedList.first.getNext();
while (thisCur != null || nodeCur != null) {
if (thisCur.getIndex() > nodeCur.getIndex()) {
nodeCur=nodeCur.getNext();
}
if (thisCur.getIndex() < nodeCur.getIndex()) {
thisCur = thisCur.getNext();
}
if (thisCur.getIndex() == nodeCur.getIndex()) {
result.add(thisCur);
thisCur = thisCur.getNext();
nodeCur = nodeCur.getNext();
}
}
return result;
}
/**
* 展示链表所有数据
*/
public void show() {
if (first.getNext() == null) {
System.err.println("链表为null");
}else{
System.out.println("当前链表长度：" + size);
Node<T> temp = first.getNext();
while (temp != null) {
System.out.println(temp.getData());
temp = temp.getNext();
}
}
}
}
@Data
@NoArgsConstructor
class Node<T> {
private int index;
private T data;
private Node<T> next;
public Node(int index, T data) {
this.index = index;
this.data = data;
}
}
@Data
@ToString
class Student{
private int no;
private int age;
private String name;
public Student(int no, int age, String name) {
this.no = no;
this.age = age;
this.name = name;
}
}
刚不经意间发现，创建的节点实例再次使用会加上子节点，导致数据混乱。如果需要加入相同的节点，需要创建值相同的不同节点实例对象