单链表(Java)

基础知识

大体结构和C++的链表差不多，参考之前写过的博客 单链表图书管理系统实例 基于类的单链表实例

补充之前不知道的：链表分两类，带和不带头结点的链表 现在才知道，Java没有像C/C++那样的指针

首先创建一个LinkList类，然后把链表的各个功能添加进去

创建结点

//当不考虑编号顺序时，找到当前链表最后节点，将最后节点next指向新节点
public void add(PersonNode node) {
    //因为头节点不能动，先需要一个辅助遍历节点temp
    PersonNode temp = head;        
    while (true) {//遍历链表，找到最后
        if (temp.next == null) {
            break;
        }            
        temp = temp.next;//如果没到最后，就继续找下去
    }//当退出while循环时，temp指向链表的最后
    temp.next = node;
}

添加结点(乱序)

public void addByOrder(PersonNode node) {
    //因为头节点不移动，仍通过一个辅助变量来找添加的位置
    //因为是单链表，所以找的temp时位于添加位置的前一个结点，否则不能插入
    PersonNode temp = head;
    boolean flag = false;//标识添加的编号是否存在
    while (true) {
        if (temp.next == null) //说明temp在链表最后
            break;
        if (temp.next.no > node.no) {//位置找到了，就在temp后面
            break;
        } else if (temp.next.no == node.no) {//希望添加的编号已存在
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag) {//编号已存在，不能添加
        System.out.println("already exist no." + node.no + ", you can't add it.=====");
    } else {
        node.next = temp.next;
        temp.next = node;
    }
}//最终还是按照序号来排列

编辑结点

public void edit(PersonNode node) {//这里直接引入外部结点，根据node.no来寻找需要修改的结点
    if (head.next == null) {
        System.out.println("empty LinkList====");
        return;
    }
    PersonNode temp;
    temp = head.next;
    boolean flag = false;//判断是否找到该结点
    while (true) {
        if (temp == null)
            break;//到了链表最后
        if (temp.no == node.no) {
            flag = true;//找到
            break;
        }
        temp = temp.next;
    }
    //根据flag判断是否找到
    if (flag) {
        temp.name = node.name;
        temp.score = node.score;
    } else {
        System.out.println("not found no." + node.no + "====");
    }
    System.out.println("=======");
}

删除结点

public void delete(int no) {
    if (head.next == null) {
        System.out.println("empty LinkList===");
        return;
    }
    PersonNode temp = head;//temp指向待删除结点的前一个结点
    boolean flag = false;
    while (true) {
        if (temp.next == null) {                
            break;//已经到链表最后
        }
        if (temp.next.no == no) {
            flag = true;//找到了待删除结点的前一个结点temp
            break;
        }
        temp = temp.next;
    }
    if (flag) {
        temp.next = temp.next.next;
    //Java会自动回收未被访问的数据        
    } else {
        System.out.println("not found====");
    }
    System.out.println("====");
}

打印链表

public void list() {
    //判断链表是否为空
    if (head.next == null) {
        System.out.println("empty LinkList=====");
        return;
    }
    //头节点不动，需要一个辅助变量来遍历
    PersonNode temp = head.next;
    while (true) {
        //判断是否到链表最后
        if (temp == null) {
            break;
        }
        //输出节点信息
        System.out.println(temp);
        //由于之前重写了toString，这里直接打印temp就可以打印出节点的所有信息
        temp = temp.next;
    }
}

主函数

public static void main(String[] args) {
    PersonNode person1 = new PersonNode(1, "Jordan", 56);
    PersonNode person2 = new PersonNode(2, "Kobe", 81);
    PersonNode person3 = new PersonNode(3, "James", 61);
    PersonNode person4 = new PersonNode(4, "Melo", 60);
    LinkList list = new LinkList();
//按照顺序添加
    // System.out.println("====add====");
    // list.add(person1);
    // list.add(person2);
    // list.add(person3);
    // list.add(person4);
//不按照顺序添加
    System.out.println("====add by order====");
    list.addByOrder(person1);
    list.addByOrder(person4);
    list.addByOrder(person3);
    list.addByOrder(person2);
    list.list();
    // list.addByOrder(person2);
    System.out.println("====edit====");
    PersonNode newNode = new PersonNode(3, "Ivring", 57);
    list.edit(newNode);
    list.list();
//删除结点
    System.out.println("====delete====");
    list.delete(4);
    list.list();
}

完整代码

//SingleLinkList.java
public class SingleLinkList {
    public static void main(String[] args) {
        PersonNode person1 = new PersonNode(1, "Jordan", 56);
        PersonNode person2 = new PersonNode(2, "Kobe", 81);
        PersonNode person3 = new PersonNode(3, "James", 61);
        PersonNode person4 = new PersonNode(4, "Melo", 60);
        LinkList list = new LinkList();
    //按照顺序添加
        // System.out.println("====add====");
        // list.add(person1);
        // list.add(person2);
        // list.add(person3);
        // list.add(person4);
    //不按照顺序添加
        System.out.println("====add by order====");
        list.addByOrder(person1);
        list.addByOrder(person4);
        list.addByOrder(person3);
        list.addByOrder(person2);
        list.list();
        // list.addByOrder(person2);
        System.out.println("====edit====");
        PersonNode newNode = new PersonNode(3, "Ivring", 57);
        list.edit(newNode);
        list.list();
    //删除结点
        System.out.println("====delete====");
        list.delete(4);
        list.list();
    }
}
//定义一个成员点
class PersonNode {
    String name;
    public int no;
    public int score;
    public PersonNode next;//指向下一个结点

    public PersonNode(int no, String name, int score) {
        this.no = no;
        this.name = name;
        this.score = score;
    }
    //为了显示方便，重写toString
    @Override
    public String toString() {
        return "[no=" + no + ",name=" + name + ",score=" + score + "]";
    }
}
//定义LinkList管理person
class LinkList {
    //初始化头节点，头节点不能动
    private PersonNode head = new PersonNode(0, "", 0);
    public PersonNode getHead(){
        return head;//返回私有成员head
    }
    //当不考虑编号顺序时，找到当前链表最后节点，将最后节点next指向新节点
    public void add(PersonNode node) {
        //因为头节点不能动，先需要一个辅助遍历节点temp
        PersonNode temp = head;        
        while (true) {//遍历链表，找到最后
            if (temp.next == null) {
                break;
            }            
            temp = temp.next;//如果没到最后，就继续找下去
        }//当退出while循环时，temp指向链表的最后
        temp.next = node;
    }

    public void addByOrder(PersonNode node) {
        //因为头节点不移动，仍通过一个辅助变量来找添加的位置
        //因为是单链表，所以找的temp时位于添加位置的前一个结点，否则不能插入
        PersonNode temp = head;
        boolean flag = false;//标识添加的编号是否存在
        while (true) {
            if (temp.next == null) //说明temp在链表最后
                break;
            if (temp.next.no > node.no) {//位置找到了，就在temp后面
                break;
            } else if (temp.next.no == node.no) {//希望添加的编号已存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {//编号已存在，不能添加
            System.out.println("already exist no." + node.no + ", you can't add it.=====");
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    public void edit(PersonNode node) {
        if (head.next == null) {
            System.out.println("empty LinkList====");
            return;
        }
        PersonNode temp;
        temp = head.next;
        boolean flag = false;//判断是否找到该结点
        while (true) {
            if (temp == null)
                break;//到了链表最后
            if (temp.no == node.no) {
                flag = true;//找到
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到
        if (flag) {
            temp.name = node.name;
            temp.score = node.score;
        } else {
            System.out.println("not found no." + node.no + "====");
        }
        System.out.println("=======");
    }
    
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("empty LinkList===");
            return;
        }
        PersonNode temp = head;//temp指向待删除结点的前一个结点
        boolean flag = false;
        while (true) {
            if (temp.next == null) {                
                break;//已经到链表最后
            }
            if (temp.next.no == no) {
                flag = true;//找到了待删除结点的前一个结点temp
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("not found====");
        }
        System.out.println("====");
        //Java会自动回收未被访问的数据
    }

    //显示链表(遍历)
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("empty LinkList=====");
            return;
        }
        //头节点不动，需要一个辅助变量来遍历
        PersonNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //由于之前重写了toString，这里直接打印temp就可以打印出节点的所有信息
            temp = temp.next;
        }
    }

}

面试题

求单链表中有效结点个数

//如果带头节点的链表，不统计头节点
public static int getLength(PersonNode head) {
    if (head.next == null)
        return 0;
    int length = 0;
    PersonNode current = head.next;//定义辅助变量
    while (current != null) {
        length++;
        current = current.next;
    }
    return length;
}

在主函数中测试

System.out.println(getLength(list.getHead()));

查找单链表中倒数第n个结点(新浪)

思路

• 编写一个方法，接收head结点，同时接收一个index
• index表示是倒数第index个结点
• 先把链表从头到尾遍历，得到链表的总长度 getLength
• 得到size后，我们从链表第一个开始遍历(size-index)

public static PersonNode findLastIndexNode(PersonNode head, int index){
    if (head.next == null)
        return null;
    int size = getlength(head);//第一次遍历，获取链表大小
    if (index <= 0 || index > size)//判断倒数的序号是否超出容量
        return null;
    PersonNode current = head.next;
    for (int i = 0; i < size - index; i++) {
        current = current.next;//遍历size-index次
    }
    return current;
}

测试

PersonNode res = findLastIndexNode(list.getHead(), 1);
System.out.println(res);

单链表反转(腾讯)

思路

• 先定义一个结点reverseHead = new PersonNode();
• 从头到尾遍历原来的链表，每遍历一个链表，就将其取出，放在新链表最前端
• 原来链表的head.next = reverseHead.next;

public static void reverseList(PersonNode head) {
    if (head.next == null || head.next.next == null)
        return;
    // 定义一个辅助遍历，帮助遍历原来的链表
    PersonNode current = head.next;
    PersonNode next = null;//指向当前结点[current]的下一个结点
    PersonNode reverseHead = new PersonNode(0, "", 0);
    while (current != null) {
        next = current.next;//先暂时保存当前结点的下一个结点，后面会用到
        current.next = reverseHead.next;//把current的下一个结点指向新链表最前端
        reverseHead.next = current;//将current连接到新链表
        current = next;//让current后移
/*每一次循环，reverseHead.next都会按照原链表的顺序定位到current，遍历结束，刚到reverseHead.next定位到链表最后一个，
此时把reverseHead.next地址赋给head.next，这样就可以倒着来遍历链表*/

    }
    head.next = reverseHead.next;//头结点拼接，实现反转
}

测试

reverseList(list.getHead());
list.list();

从尾到头打印单链表(百度)

思路

• 1.先反转后再打印(有个问题：只要求逆序打印，不要求反转，这样会破坏原链表结构)
• 2.用栈的方法，利用栈先进后出的特点，实现逆序打印的效果

stack.java

下面是栈的实例

import java.util.Stack;
public class stack{
    public static void main(String[] args){
        Stack<String> stack = new Stack<>();
        stack.add("James");
        stack.add("Kboe");
        stack.add("Jordan");
        while(stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}

用栈的方法实现从头到尾打印单链表

public static void reversePrint(PersonNode head) {
    if (head.next == null)
        return;
    //创建一个栈，将各个结点压入栈
    Stack<PersonNode> stack = new Stack<PersonNode>();
    PersonNode current = head.next;
    while (current != null) {
        stack.push(current);
        current = current.next;
    }
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

测试

reversePrint(list.getHead());