单链表按照指定顺序插入节点(思路分析) [数据结构][Java]

单链表按照特定顺序插入节点(思路分析)

这里我们要实现在自定义的英雄链表中添加英雄时,根据排名将英雄插入到指定位置(如果有链表中已经有这个排名了,那么就添加失败,并且给出提示)

思路分析:

1. 首先找到待添加结点位置的前一个位置

   • 涉及到遍历:所以是通过辅助变量(指针)来实现的
     • 因为涉及到单链表遍历,要遍历就要通过辅助变量来完成
   • 注意: 这里我们找到的一定要是待添加结点的前一个位置的结点,因为这个时候我们是要实现插入操作,那么这个时候我们要修改插入节点的前一个位置的结点的数据域,那么我们要修改插入节点的前一个位置的节点的指针域首先我们就是要获得待插入节点的前一个位置的结点

2. 插入节点
   ① 待插入节点.next = temp.next

   • 我们这一步就是先将待插入节点的尾部和原本表中待插入位置的后一个节点相连接

   ②temp.next = 待插入节点

   • 我们这一步就是先将带插入节点的头部和原本表中待插入位置的前一个节点相连

• 注意: 这里的①②两步不可以交换位置,这个时候涉及到了一个小的算法
• temp是辅助指针

补充:

辅助指针是从头结点开始的,因为我们可能插入的位置就是在头结点之后,如果我们要待插入的位置是在头结点之后,那么这个时候我们就要修改待插入节点的前一个位置的结点的指针域,那么其实就是我们要能获取到头结点,所以我们要从头结点开始查找 --> 也就是 temp = head;

• head是头结点

我们如果添加元素的时候是按照某个属性升序的方式进行添加,这个时候我们并且是从前往后查找要添加的位置那么我们要判断出这个待添加结点的位置,我们肯定是要通过表中的结点的此属性 > (大于) 待插入节点的此属性作为临界条件 —> 因为我们还是从前往后查找,这个时候前面都是值小的元素,这个时候前面可能有很多个结点的此属性值都比待插入节点的此属性值要小,所以我们要通过 > (大于)条件来判断 —> 这样就可以查找到待插入节点的后一个节点位置 —> 但是我们的辅助变量又是指向待插入节点的前一个位置的结点的,那么我们要怎么办?

• 我们可以使用temp(辅助变量).next就是表示待插入节点的后一个位置了 —> 所以我们就可以写成: temp.next.no > heroNode.no

对于我们按照特定顺序添加元素的情况,这个时候我们如果我们的链表中有重复编号,这个时候就表示添加失败,并且给出提示

我们在对链表中进行按照顺序添加元素的时候我们可以先在遍历链表,找到我们要添加的结点的位置,并且我们一定要定义一个boolean类型的变量flag,如果在添加的这个元素的编号在链表中已经有了,这个时候就将flag的值设置为true,也就是flag的值为true表示添加失败,如果想要添加的元素编号再链表中不存在,也就是编号没有重复,这个时候我们就首先要将这个插入位置的前一个节点返回,然后再将flag变量的值设置为false —> 然后我们就可以根据flag变量的值确定我们是否要添加元素,并且添加的位置我们已经是知道了,所以如果flag为true的话那么就直接输出一个添加失败,如果flag的值为false的时候这个时候我们就进行结点的添加操作,我们只要将我们的待添加结点插入到指定的位置中去就可以了