- 单链表基础练习
- 提供节点类
- 获取单链表节点个数
- 查找倒数第k个节点
- 反转单链表
- 从尾到头打印链表
- 合并两个单向链表，并且按照顺序合并
- 总结
class NewInteger{
private int number;
private NewInteger next;
public NewInteger(int number){
this.number = number;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
public NewInteger getNext() {
return next;
}
public void setNext(NewInteger next) {
this.next = next;
}
public String toString(){
return "["+number+"]";
}
}
获取单链表节点个数
public int getCount() {
//创建辅助节点，循环
NewInteger temp = head.getNext();
int count = 0;
while (temp != null) {
count++;
//辅助节点后移
temp = temp.getNext();
}
return count;
}
查找倒数第k个节点
// 查找倒数第几个节点
public NewInteger getLastP(int index){
NewInteger temp = head.getNext();
if (index <= 0 || index > this.getCount(){
return null;
}
for (int i = 0; i < getCount()-index; i++){
temp = temp.getNext();
}
return temp;
}
反转单链表
//两种方式：如下
//反转链表(指针指向反转)
public void reverseLinked(){
//当前节点的前一个节点
NewInteger pre = null;
//当前节点
NewInteger temp = head.getNext();
//当前节点后一个节点
NewInteger next;
//如果链表没有节点，或只有一个节点，不用反转
if (temp == null || temp.getNext() == null){
return;
}
//循环到当前节点为null时结束
while (temp != null){
//保留当前节点的下一节点信息
next = temp.getNext();
//将当前节点的下一节点指向他的前一节点
temp.setNext(pre);
//pre后移
pre = temp;
//temp后移
temp = next;
}
//将头节点后一个节点设置为pre
head.setNext(pre);
}
/
//反转链表使用栈
public void reverseByStack(){
NewInteger temp = head.getNext();
Stack newInteger = new Stack<>();
//链表为空或只有一个节点则不用反转
if (temp == null || temp.getNext() == null){
return;
}
while (temp != null){
newInteger.push(temp);
temp = temp.getNext();
}
while (newInteger.size() != 0){
System.out.println(newInteger.pop());
}
}
合并两个单向链表，并且按照顺序合并
public static IntegerLinked getOneLinked(IntegerLinked linked1, IntegerLinked linked2) {
//传入两个链表对象，拿到其各自的头节点
NewInteger head1 = linked1.getHead();
NewInteger head2 = linked2.getHead();
//判断特殊情况
if (head1.getNext() == null) {
return linked2;
}
if (head2.getNext() == null) {
return linked1;
}
//辅助节点，循环
NewInteger temp = head1.getNext();
while (temp.getNext() != null) {
temp = temp.getNext();
}
//找到最后一个节点位置，将他的下一节点指向，另一链表的第一个节点
temp.setNext(head2.getNext());
//返回合并后的节点
return linked1;
}
上面的代码，对我们传入的两个链表进行了常规合并，接下来提供两种排序写法：
public void sortLinked2() {
NewInteger temp = head.getNext();
//如果链表为空，或链表只有一个节点
if (temp == null || temp.getNext() == null) {
return;
}
//冒泡排序
for (int i = 0; i < getCount() - 1; i++) {
//每次从头开始循环，重新定义辅助节点
temp = head.getNext();
for (int j = 0; j < getCount() - 1 - i; j++) {
if (temp.getNumber() > temp.getNext().getNumber()) {
//保留较小节点值
int number = temp.getNumber();
//对当前节点进行内容修改
temp.setNumber(temp.getNext().getNumber());
//对后一节点进行内容修改
temp.getNext().setNumber(number);
}
//辅助节点后移
temp = temp.getNext();
}
}
}
public void sortLinked1() {
NewInteger temp = head.getNext();
//如果链表为空，或链表只有一个节点
if (temp == null || temp.getNext() == null) {
return;
}
//设置为当前节点的前一节点
NewInteger pre = null;
//设置当前节点的后一节点
NewInteger next = null;
for (int i = 0; i < getCount() - 1; i++) {
temp = head.getNext();
pre = null;
for (int j = 0; j < getCount() - 1 - i; j++) {
//冒泡排序，相邻两数进行比较
//若当前节点小于后一节点，则pre，temp后移
if (temp.getNumber() <= temp.getNext().getNumber()) {
pre = temp;
temp = temp.getNext();
} else {//如果大于
//将当前节点的后一节点取出（提取）
next = temp.getNext();
//设置当前节点的后一节点为，原后一节点的后一节点（指向下下节）
temp.setNext(next.getNext());
//重新设置当前后一节点的后一节点为此节点（调换顺序，原下一节指向当前节）
next.setNext(temp);
/
public void add(NewInteger integer) {
//创建循环辅助节点
NewInteger temp = head.getNext();
//判断链表是否有节点
if (temp == null) {
head.setNext(integer);
return;
}
//链表不为空的情况下
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(integer);
}
public void listAll() {
NewInteger temp = head.getNext();
if (temp == null) {
System.out.println("链表为空！！！");
return;
}
System.out.print("[");
while (temp != null) {
System.out.print(temp);
temp = temp.getNext();
}
System.out.println("]");
}
public void sortLinked2() {
NewInteger temp = head.getNext();
//如果链表为空，或链表只有一个节点
if (temp == null || temp.getNext() == null) {
return;
}
for (int i = 0; i < getCount() - 1; i++) {
temp = head.getNext();
for (int j = 0; j < getCount() - 1 - i; j++) {
if (temp.getNumber() > temp.getNext().getNumber()) {
int number = temp.getNumber();
temp.setNumber(temp.getNext().getNumber());
temp.getNext().setNumber(number);
}
temp = temp.getNext();
}
}
}
public void sortLinked1() {
NewInteger temp = head.getNext();
//如果链表为空，或链表只有一个节点
if (temp == null || temp.getNext() == null) {
return;
}
//设置为当前节点的前一节点
NewInteger pre = null;
//设置当前节点的后一节点
NewInteger next = null;
for (int i = 0; i < getCount() - 1; i++) {
temp = head.getNext();
pre = null;
for (int j = 0; j < getCount() - 1 - i; j++) {
//冒泡排序，相邻两数进行比较
//若当前节点小于后一节点，则pre，temp后移
if (temp.getNumber() <= temp.getNext().getNumber()) {
pre = temp;
temp = temp.getNext();
} else {//如果大于
//将当前节点的后一节点取出（提取）
next = temp.getNext();
//设置当前节点的后一节点为，原后一节点的后一节点（指向下下节）
temp.setNext(next.getNext());
//重新设置当前后一节点的后一节点为此节点（调换顺序，原下一节指向当前节）
next.setNext(temp);
/
public int getCount() {
//创建辅助节点，循环
NewInteger temp = head.getNext();
int count = 0;
while (temp != null) {
count++;
//辅助节点后移
temp = temp.getNext();
}
return count;
}
}
class NewInteger{
private int number;
private NewInteger next;
public NewInteger(int number){
this.number = number;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
public NewInteger getNext() {
return next;
}
public void setNext(NewInteger next) {
this.next = next;
}
public String toString(){
return "["+number+"]";
}
}
运行结果图：
