一、链表的定义

链表是一种递归的数据结构，是一种线性结构，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)，简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里，它们可以不是连续的因为他们每个节点保存着下一个节点的引用（地址）

二、链表的类型

单链表（注意：这里通常使用的是带有头结点的单链表，头结点不能动，需要使用辅助节点，如果头结点动了，那头结点所指的原来的数据就会丢失）

头结点和头指针的区别？

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理。

优势1：第1个位置的插入、删除更加方便，带来操作上的统一
例如：head为头指针，x待插入(后插方式)的新结点，p为指向任意结点的指针。
对于带头结点的插入到第一个位置的代码：
p = head;
x->next = head->next;
head->next = x;
插入其他结点
x->next = p->next;
p->next = x;
若令p=head，则带有头结点的链表，可以实现代码复用，减少分支。
对于不带头结点的插入到第一个位置的代码：
x->next = head->next;
head = x;//这里有差异
插入其他结点
x->next = p->next;
p->next = x;
因此，不带头结点的链表，插入第一个结点时，需要特殊处理，删除操作类似。
优势2:统一空表和非空表的处理
若使用头结点，无论表是否为空，头指针都指向头结点，也就是*LNode类型，对于空表和非空表的操作是一致的。
若不使用头结点，当表非空时，头指针指向第1个结点的地址，即*LNode类型，但是对于空表，头指针指向的是NULL，此时空表和非空表的操作是不一致的。
所以单链表一般为带头结点的单链表。

• 
  

  1、定义

单链表(又称单向链表)是链表中的一种，其特点是链表的链接方向是单向的，对链表的访问要从头部(head)开始，然后依次通过next指针读取下一个节点。

• 2、数据结构

单链表的数据结构可以分为两部分：数据域和指针域，数据域存储数据，指针域指向下一个存储节点的地址。注意: 单向链表只可向一个方向进行遍历

• 3、节点代码描述

//定义一个HeroNode,每个HeroNode对象就是一个结点
class HeroNode{
    public int no;
    public String name;
    public String nickname;//昵称
    public HeroNode next;//指向下一个节点
    public HeroNode(int no, String name, String nickname) {
        super();
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    //为了显示方便重写一下toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname +  "]";
    }   
}

双链表

• 1、定义

双链表(又称双向链表)，是链表中一种，与单链表不同的是它的每个节点都有两个指针，分别指向直接后继节点和直接前驱节点；所以，从双链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

• 2、数据结构

双链表的数据结构可以分为三部分：prev指针域、数据域和next指针域，prev指针域指向上一个存储节点的地址(也即指向直接前驱节点),数据域存储数据，next指针域指向下一个存储节点的地址(也即指向直接后继节点)。注意: 单向链表可向两个方向进行遍历,分别为正序和逆序遍历

• 3、节点代码描述

// 定义 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode { 
    public int no; 
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点,默认为 null 
    public HeroNode pre;// 指向前一个节点,默认为 null
    public HeroNode(int no, String name, String nickname) { 
    this.no = no;
    this.name = name; 
    this.nickname = nickname;
    }
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }
}

单向循环链表

• 1、定义

单向循环链表，只是在单链表的基础上，它的最后一个结点不再为null而是指向头结点，形成一个环。并且在节点结构上和单链表是一样的。因此，从单向循环链表中的任何一个结点出发都能找到任何其他结点。

• 2、数据结构

  3、结点代码描述

class BoyNode{
    //编号
    private int no;
    //指向下一个节点,默认为空
    private BoyNode next;
    public BoyNode(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public BoyNode getNext() {
        return next;
    }
    public void setNext(BoyNode next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "BoyNode{" +
                "no=" + no +
                ", next=" + next +
                '}';
    }
}

• 1、定义双向循环链表，只是在双链表的基础，它的头节点的prev指针不再为null，而是直接指向它的尾节点；它的尾节点的next指针不再为null，而是直接指向它的头节点。

• 2、数据结构

  
  

三、链表的特点

• 1、在内存中不是连续的内存地址空间，它只是一种逻辑上的线性连续结构。每个节点都含有指向下一个节点的next指针(可能指向下一个节点或null)

• 2、链表在节点的删除和增加有着很高效率，基本是O(1)常数级的时间效率，而顺序表实现删除和增加操作则是线性级O(n)的时间效率。所以一般用于用于元素节点频繁删除和增加

• 3、而对于链表的查找和获得第K个链表中节点，往往需要采用遍历的方式实现，所以一般需要O(n)的时间效率

• 4、链表长度是可变的，也就意味着在内存空间足够范围内，链表长度可以无限扩大。而顺序表则一般是固定的，当超出长度的时候则会进行扩容。

四、链表的基本操作

1) 第一种方法在添加英雄时，直接添加到链表的尾部 思路分析图:

2) 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:

3) 修改节点功能

思路(1) 先找到该节点，通过遍历，(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname 3) 删除节点思路分析的示意图:

//定义一个SingleLinkedList,管理HeroNode
class SingleLinkedList{
    //初始化一个头结点,不存放具体的数据，头结点不要动，否则之后就找不到链表了
    private HeroNode head=new HeroNode(0, "", "");
    public HeroNode getHead() {
        return head;
    }
    //添加节点到单向链表,默认不考虑no(排名),直接添加到尾部
    //当不考虑编号的顺序时，找到当前链表的最后节点
    //将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此需要一个辅助变量temp
        HeroNode temp=head;
        //遍历找到最后
        while(true) {
            if(temp.next==null) {
                break;
            }
            temp=temp.next;
        }
        //当退出while循环的时候，temp就指向了链表的最后
        temp.next=heroNode;
    }
    //按照排名no进行添加，如果no已经存在则提示
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp=head;//因为head节点不能动，因此需要一个辅助变量temp
        //我们要找的位置为当前需要添加节点的前一个节点
        boolean flag=false;//添加的no是否存在，默认为false
        while(true) {
            if(temp.next==null) {
                //说明temp在表尾，此时直接break
                break;
            }
            if(temp.next.no>heroNode.no) {
                //位置找到了，就在temp的后面插入
                break;
            }else if(temp.next.no==heroNode.no) {
                //该no已经存在了
                flag=true;//说明编号已经存在
                break;
            }
            temp=temp.next;//后移遍历当前链表
        }
        //判断flag的值
        if(flag) {
            System.out.println("准备插入的英雄的编号"+heroNode.no+"已经存在，不能添加");
        }else {
            //加入到链表中，temp的后面
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }
    //修改节点的系信息，注意no不能变化，因为需要根据编号进行新修改
    public void update(HeroNode heroNode) {
        //判断是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no的编号
        HeroNode temp =head.next;
        boolean flag=false;//表示是否找到该节点
        while(true) {
            if(temp==null) {
                break;//到链表的尾部了，遍历完毕,没有找到
            }
            if(temp.no==heroNode.no) {
                //找到的话
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根据flag判断是否找到需要修改的节点
        if(flag) {
            temp.name=heroNode.name;
            temp.nickname=heroNode.nickname;
        }else {
            //没有找到
            System.out.println("没有找到编号为"+heroNode.no+"的节点");
        }
    }
    //遍历显示链表
    public void list() {
        //判断链表是否为空
        if(head.next==null) {
            System.out.println("链表为空");
            return;
        }
        //因为头结点不能动，使用一个辅助变量进行遍历
        HeroNode temp=head.next;//上面如果不为空，至少有一个数据,可以遍历head.next
        while(true) {
            //判断是否到链表的最后
            if(temp==null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp); //因为已经重写了HeroNode的toString方法，这里可以直接输出
            //将next后移
            temp=temp.next;
        }
    }
 //删除节点,找到需要删除节点的前一个节点,注意我们在比较的时候是使用temp.next.no和删除节点的no比较，如果是用temp.no则没法找到上一个了
    //被删除的节点，将不会有其他的指向，会被垃圾回收机制释放
    public void delete(int no) {
        HeroNode temp=head;
        boolean flag=false;//表示是否找到待删除节点
        while(true) {
            if(temp.next==null) {//已经到链表的最后
                break;
            }
            if(temp.next.no==no) {
                //找到待删除节点的前一个节点temp
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag) {//找到，删除
            temp.next=temp.next.next;
        }else {
            System.out.println("要删除的节点不存在");
        }
    }
}

4.2使用带 head 头的双向链表实现 –水浒英雄排行榜

Ø    管理单向链表的缺点分析:

2) 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).

对上图的说明:

分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现

1)  遍历 方和 单链表一样，只是可以向前，也可以向后查找

2)  添加 (默认添加到双向链表的最后)

    (1) 先找到双向链表的最后这个节点

(2)  temp.next = newHeroNode

(3)  newHeroNode.pre = temp;

3)  修改 思路和 原来的单向链表一样.
4) 删除

    (1) 因为是双向链表，因此，我们可以实现自我删除某个节点

    (2)  直接找到要删除的这个节点，比如 temp

(3)       temp.pre.next = temp.next

(4)  temp.next.pre = temp.pre;

双向链表的代码实现

public class DoubleList {
	public static void main(String[] args) {
		//创建节点
		DoubleHeroNode h1=new DoubleHeroNode(1,"宋江","呼保义");
		DoubleHeroNode h2=new DoubleHeroNode(2,"吴用","智多星");
		DoubleHeroNode h3=new DoubleHeroNode(3,"林冲","豹子头");
		DoubleHeroNode h4=new DoubleHeroNode(4,"卢俊义","玉麒麟");
		//初始化一个双向链表
		DoubleLinkedList list=new DoubleLinkedList();
		list.addDoubleHeroNode(h1);
		list.addDoubleHeroNode(h2);
		list.addDoubleHeroNode(h3);
		list.addDoubleHeroNode(h4);
		System.out.println("1.遍历双向链表");
		list.showDoubleList();
		System.out.println("2.修改双向链表里面的节点");
		DoubleHeroNode h5=new DoubleHeroNode(4,"鲁智深","花和尚");
		list.updateDoubleHeroNode(h5);
		list.showDoubleList();
		System.out.println("3.删除双向链表中的一个节点");
		list.deleteDoubleHeroNode(3);
		list.showDoubleList();
	}
}
class DoubleLinkedList{
	//初始化一个头结点，头结点不要动，不存放具体的数据
	private DoubleHeroNode head=new DoubleHeroNode(0,"","");
	//返回头结点
	public DoubleHeroNode getHeadNode(){
		return head;
	}
	//1.遍历双向链表
	public void showDoubleList(){
		if(head==null){
			//链表为空
			System.out.println("链表为空");
			return;
		}else{
			//定义一个辅助节点
			DoubleHeroNode temp=head.next;
			while (temp!=null){
				System.out.println(temp);
				temp=temp.next;
			}
		}

	}
	//2.添加节点到双向链表最后
	public void addDoubleHeroNode(DoubleHeroNode node){
		//定义一个辅助节点指向头结点,这里为什么不用temp=head.next呢，因为上面没有判断head是否有next
		DoubleHeroNode temp=head;
		while(true){
			//判断是否还有下一个节点，如果没有下一个节点说明跑到最后了
			if(temp.next==null){
				break;
			}
			temp=temp.next;
		}
		//把新节点插入到最后
		temp.next=node;
		node.pre=temp;
	}
	//3.修改双向链表的节点
	public void updateDoubleHeroNode(DoubleHeroNode node){
		//定义一个辅助接点指向head
		if(head.next==null){
			System.out.println("链表为空");
			return;
		}
		DoubleHeroNode temp=head.next;
		//找到需要修改的位置
		while(true){
			if(temp.no==node.no){
				//找到
				temp.name=node.name;
				temp.nickname=node.nickname;
				break;
			}
			//判断是否为空
			if(temp.next==null){
				System.out.println("已经遍历到链表尾部");
				break;
			}else{
				//向下找
				temp=temp.next;
			}
		}
	}
	//4.从双向链表根据no删除一个节点
	public void deleteDoubleHeroNode(int no){
		if(head.next==null){
			System.out.println("空链表，无法删除");
			return;
		}
		//定义一个辅助节点
		DoubleHeroNode temp=head.next;
		while (true){
			if(temp.no==no){
				//找到
				temp.pre.next=temp.next;
				//这里不能直接使用temp.next，如果是最后一个节点会出现空指针异常
				if(temp.next!=null){
					temp.next.pre=temp.pre;
				}
				break;
			}
			if(temp.next!=null){
				temp=temp.next;
			}else{
				System.out.println("没找到要删除的节点");
				break;
			}
		}
	}
}

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由 此产生一个出队编号的序列。

Ø 约瑟夫问题的示意图

Ø  Josephu 问题

结点从链表中删除算法结束。

约瑟夫问题-小孩出圈的思路分析图

public class RoundList {
    public static void main(String[] args) {
        CircleList circleList = new CircleList();
        //加入5个小孩节点
        circleList.addBoy(5);
        circleList.showList();
        //测试出圈
        circleList.countBoy(1,2,5);
    }
}
class CircleList{
    //创建一个first节点，当前没有编号
    private BoyNode first=null;
    //添加小孩节点，构建一个环形链表
    public void addBoy(int nums){
        //nums代表小孩的个数,至少有一个小孩
        if(nums<1){
            System.out.println("nums的值不正确");
            return;
        }
        //辅助指针，帮助构建环形链表
        BoyNode curBoy=null;
        //创建环形链表,编号从1开始
        for(int i=1;i<=nums;i++){
            //根据编号创建小孩节点
            BoyNode boyNode=new BoyNode(i);
            //如果是第一个小孩，自己需要构成一个环状
            if(i==1){
                first=boyNode;
                //构成环状
                first.setNext(first);
                //让辅助变量指向第一个节点
                curBoy=first;
            }else{
                //1.设置当前链表的下一个节点
                curBoy.setNext(boyNode);
                //2.让新加入的最后节点指向第一个节点
                boyNode.setNext(first);
                //3.更新辅助节点
                curBoy=boyNode;
            }
        }
    }
    //遍历环形链表
    public void showList(){
        //判断链表是否为空
        if(first==null){
            System.out.println("没有任何节点，链表为空");
            return;
        }
        //因为first不能动，因此需要使用一个辅助指针完成遍历
        BoyNode curBoy=first;
        while (true){
            System.out.println("小孩的编号"+curBoy.getNo());
            //如果curBoy.getNext为第一个，说明到了链表尾部
            if (curBoy.getNext()==first){
                break;
            }
            //循环后移
            curBoy=curBoy.getNext();
        }
    }
    //根据用户的输入，计算出小孩出圈的顺序
    //startNo表示从第几个小孩开始
    //countNum 表示数几下
    //nums表示几个小孩在圈中
    public void countBoy(int startNo,int countNum,int nums){
        //先对数据进行校验
        if(first==null||startNo<1||startNo>nums){
            System.out.println("错误");
            return;
        }
        //创建一个辅助指针，帮助完成小孩出圈
        BoyNode helper=first;
        //让helper指向最后一个节点
        while(true){
            if(helper.getNext()==first){
                break;
            }
            helper=helper.getNext();
        }
        //报数前先让first和helper移动到开始报数的小孩
        for(int j=0;j<startNo-1;j++){
            first=first.getNext();
            helper=helper.getNext();
        }
        //让helper和first移动countNum-1次之后让小孩出圈,countNum-1因为自己要数一次
        //这里是一个循环操作，直到圈中只有一个小孩
        while(true){
            if(helper==first){
                System.out.println("只有一个小孩了");
                break;
            }
            for (int j=0;j<countNum-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }
            //这时first指向的节点就是要出圈小孩的节点
            System.out.println("小孩"+first.getNo()+"出圈");
            first=first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中小孩的编号是"+first.getNo());
    }
}

五、链表实现栈和队列数据结构

1、链表实现栈结构

由于栈是一个表，因此任何实现表的方法都能实现栈。显然，Java中常用的ArrayList和LinkedList集合都是支持栈操作的。

• 实现思路

单链表也是能实现栈的，通过在表的顶端插入实现栈的push压栈操作，通过删除表的顶端元素实现pop入栈操作。top操作只需要返回顶部的元素的值即可。

• 实现代码

class LinkedStack {
    private var first: Node? = null
    private var len: Int = 0

    fun push(value: Int) {//相当于链表从表头插入新的元素
        val oldFirst = first
        first = Node(value)
        first?.next = oldFirst
        len++
    }

    fun pop(): Int {//相当于链表从表头删除新的元素
        val value = first?.value
        first = first?.next
        return value ?: -1
    }

    fun top(): Int {
        return first?.value ?: -1
    }

    fun isEmpty(): Boolean {
        return first == null
    }

    fun size(): Int {
        return len
    }

    inner class Node(var value: Int) {
        var next: Node? = null
    }
}

2、链表实现队列结构

class LinkedQueue {
    private var first: Node? = null
    private var last: Node? = null
    private var len: Int = 0

    fun enqueue(value: Int) {//相当于链表从尾部插入新的节点
        val oldLast = last
        last = Node(value)
        last?.next = null
        if (isEmpty()) {
            first = last
        } else {
            oldLast?.next = last
        }
        len++
    }

    fun dequeue(): Int {//相当于链表从尾部删除最后节点
        val value = first?.value ?: -1
        first = first?.next
        if (isEmpty()) {
            last = null
        }
        return value
    }

    fun isEmpty(): Boolean {
        return first == null
    }

    fun size(): Int {
        return len
    }

    inner class Node(var value: Int) {
        var next: Node? = null
    }
}

六、链表中经典快慢指针问题

快慢指针追赶问题在链表中是非常经典的，快慢指针问题一般用于解决链表中间节点问题和链表是否含有环以及链表中环的入口位置等问题。

如果使用快慢指针是判断链表是否含有环的问题，我们更希望fast和slow指针的相对路程是正好是环的长度，(也就是slow指针刚进入环，而fast指针刚绕环一圈，此时两指针正好相遇)这样两个指针就相遇了。这样取每步的速度差能够被环长度整除的数字。但是我们并不知道环的具体长度，所以只能取每步的速度差能够被环长度整除的数字为1(1能被所有的数整除),所以我们取fast指针每次走2步，slow指针每次走1步，实际上只要保证两者速度差为1就可以了，你甚至可以fast每次走3步，slow指针每次走2步都是可以的，这样一来只要它们在环里面就一定能相遇。

1、快慢指针与链表环问题

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;//慢指针每次走1步
            fast = fast.next.next;//快指针每次走2步
            if(slow == fast){//如果链表存在环，那么slow和fast指针会相遇
                return true;
            }
        }

        return false;
    }

2、快慢指针找中间节点问题

由快慢指针追赶的原理可知，如果fast指针和slow指针同时从链表(链表不含环)的头结点出发开始遍历，如果fast指针的每次遍历步数是slow指针的两倍，那么可得到如果fast遍历到链表的尾部，那么此时的slow指针应该处于链表的中间节点位置(具体题目可参考：LeetCode第876题)。

    public ListNode middleNode(ListNode head) {
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

七、单链表面试题目

单链表相关的面试题目

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建结点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(6, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(4, "李逵", "黑旋风");
        HeroNode hero6 = new HeroNode(5, "晁盖", "托塔天王");
        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        //按照在尾部插入的方法添加
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        singleLinkedList2.add(hero5);
        singleLinkedList2.add(hero6);
        //按照no进行添加
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);
        //显示
        //singleLinkedList.list();
        //测试修改节点的代码
        //HeroNode hero=new HeroNode(2,"卢某","玉麒麟~");
        //singleLinkedList.update(hero);
        //显示
        //singleLinkedList.list();
        //删除
        //singleLinkedList.delete(1);
        //显示
        //singleLinkedList.list();
        //测试一下,求单链表中有效节点的个数
        //System.out.println("有效的节点个数为"+getLength(singleLinkedList.getHead()));
        //测试一下看看是否得到了倒数第k个节点
        //int n=2;
        //System.out.println("这是倒数第"+n+"个节点"+findLastIndexNode(singleLinkedList.getHead(), n));
        //测试单链表的反转
		System.out.println("反转之前的");
		singleLinkedList.list();
		System.out.println("反转之后的");
		reversetList(singleLinkedList.getHead());
		singleLinkedList.list();
        //测试逆序打印单链表,本身的顺序并没有发生变化
        //reversePrint(singleLinkedList.getHead());
        //测试两个有序链表的合并
        combineTwo(singleLinkedList.getHead(), singleLinkedList2.getHead());

    }
    //查找单链表的倒数第k个节点
    //1，先遍历链表，得到链表的长度，得到length之后，从第一个开始遍历到size-index就可以得到
    public static HeroNode findLastIndexNode(HeroNode head,int index) {
        if(head.next==null) {
            return null;//链表为空,没找到
        }
        //第一个遍历得到链表的长度
        int size=getLength(head);
        //第二次遍历到size-index就是我们要找的结果
        if(index<=0||index>size) {
            return null;
        }
        HeroNode temp=head.next; //定义一个辅助变量,这里使用next的原因是上面求size的时候没有算头结点，所以用head.next
        for(int i=0;i<size-index;i++) {
            temp=temp.next;
        }
        return temp;
    }
    //2.获取到单链表的节点的个数(如果是带有头结点的链表，不统计头结点)
    //head表示链表的头结点,返回值为有效节点的个数
    public static int getLength(HeroNode head) {
        if(head.next==null) {
            //说明这是一个带有头结点的空链表
            return 0;
        }
        //定义一个辅助变量
        HeroNode cur=head.next;
        int length=0;
        while(cur!=null) {
            length++;
            cur=cur.next;
        }
        return length;
    }
    //3,反转链表，
    public static void reversetList(HeroNode head) {
        //如果当前链表为空或者只有一个结点，无需反转
        if(head.next==null||head.next.next==null) {
            return ;
        }
        HeroNode curr=head.next;//定义一个辅助指针，帮助我们遍历原来链表
        HeroNode next=null; //指向当前节点的下一个节点
        HeroNode reverseHead=new HeroNode(0,"","");
        //从头遍历原来的节点，每遍历一个基点，就将其取出来，并放在新的链表的reverseHead的最前端
        while(curr!=null) {
            next=curr.next; //暂时保存当前节点的下一个节点
            curr.next=reverseHead.next; //将curr的下一个节点指向链表的最前端
            reverseHead.next=curr;//将新的节点连接到反转链表上
            curr=next;//让curr后移
        }
        //将head.next指向reverseHead.next,实现单链表的反转
        head.next=reverseHead.next;
    }
    //4,利用栈实现链表的反转输出
    public static void reversePrint(HeroNode head) {
        if(head.next==null) {
            return;//空链表不打印
        }
        //创建一个栈，将各个节点压栈
        Stack stack=new Stack<HeroNode>();
        HeroNode temp=head.next;
        //将链表中所有节点压栈
        while(temp!=null) {
            stack.push(temp);//压栈
            temp=temp.next;//后移
        }
        //逆序打印，也就是出栈的过程
        while(stack.size()>0) {
            System.out.println(stack.pop());
        }
    }
    //5.合并两个有序的链表
    public static HeroNode combineTwo(HeroNode n1,HeroNode n2 ) {
        HeroNode temp1=n1.next;
        HeroNode temp2=n2.next;
        HeroNode head=new HeroNode(0,"","");
        HeroNode cur=head;
        while(temp1!=null&&temp2!=null) {
            if(temp1.no<temp2.no) {
                cur.next=temp1;
                temp1=temp1.next;
            }else {
                cur.next=temp2;
                temp2=temp2.next;
            }
            cur=cur.next;
        }
        if(temp1==null) {
            cur.next=temp2;
        }
        if(temp2==null) {
            cur.next=temp1;
        }
        head=head.next;
        while(head!=null) {
            System.out.println(head.no+head.name);
            head=head.next;
        }
        return cur;
    }
}