单链表

单链表

• 链表是以节点方式存储的。
• 每个节点包含data域，next域。next域指向下一个节点。
• 链表中的各个节点不一定是连续存储，如图所示：

• 链表分为带头节点的链表和没有头节点的链表，根据实际需求来确定。

代码实现（java）

• 代码中包含了基本的添加节点、修改节点信息、删除节点、查找节点。除此之外还包含一些其他的功能。

节点类：

class Node {
    public int no;
    public String name;
    public String nickName;
    public Node next;

    public Node(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }
}
复制代码

链表类：

class SignalLinkedList {
    private Node head = new Node(0, "", "");

    //尾插法插入节点
    public void addNode(Node node) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        node.next = null;
    }

    //按no顺序插入
    public void addOrderNode(Node node) {
        Node temp = head;
        //遍历链表，寻找符合条件的节点
        while (temp.next != null) {
            if (temp.next.no > node.no) {
                node.next = temp.next;
                temp.next = node;
                return;
            } else {
                temp = temp.next;

            }
        }
        //此时可能是链表为空，也可能是链表中的节点均不满足条件，将新节点直接添加即可。
        if (temp.next == null) {
            temp.next = node;
            node.next = null;
        }
    }

    //修改节点的值，此处要用no做判断，no不能被修改
    public void changeNode(int no, String name, String nickName) {
        Node temp = head;
        Boolean flag = false;
        if (temp.next == null) {
            System.out.println("链表为空不能修改！");
        }
        while (temp.next != null) {
            if (temp.next.no == no) {
                temp.next.name = name;
                temp.next.nickName = nickName;
                flag = true;
            }
            temp = temp.next;
        }
        if (flag == false) {
            System.out.println("链表中没有该节点！");
        }
    }

    //根据no删除对应节点
    public void del(int no) {
        Node temp = head;
        Boolean flag = false;
        if (temp.next == null) {
            System.out.println("链表为空，不能删除！");
        }
        while (temp.next != null) {
            if (temp.next.no == no) {
                temp.next = temp.next.next;
                flag = true;
            }
            temp = temp.next;
        }
        if (flag == false) {
            System.out.println("链表中没有该节点！");
        }
    }

    //遍历输出链表中节点信息
    public void showLinkedList() {
        Node temp = head;
        if (temp.next == null) {
            System.out.println("链表为空！！！");
        }
        while (temp.next != null) {
            System.out.printf("no = %d name = %s nickName = %s;\n", temp.next.no, temp.next.name, temp.next.nickName);
            temp = temp.next;
        }
    }

    //求单链表中有效节点的个数
    public int nodeNum() {
        Node temp = head;
        int length = 0;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return  length;
    }

    //查找单链表中的倒数第k个节点
    public Node reciprocalKNode(int k) {
        Node fast = head;
        Node slow = head;
        int length = 0;
//        for (int i = 0; i < k-1; i++) {
//            fast = fast.next;
//        }
        //定义两个辅助节点，使其中一个节点处于比另一个节点快k-1个节点的位置，然后使两个节点同时循环直到快的节点到链表的最后，此时慢的节点所在的位置即为倒数第k个节点
        while (fast.next != null) {
            if (length != k-1) {
                fast = fast.next;
                length++;
                continue;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //单链表的反转
    public void reverseLinkedList(SignalLinkedList List) {
        Node reverseHead = new Node(0, "", "");
        Node listTemp = List.head.next;
        Node next = null;
        while (listTemp != null) {
            next = listTemp.next;
            listTemp.next = reverseHead.next;
            reverseHead.next = listTemp;
            listTemp = next;
        }
        List.head.next = reverseHead.next;
    }
}
复制代码

main函数中：

package com.linkedlist;

public class LinkedList {
    public static void main(String[] args) {
        //尾插法加入节点，不按照顺序
        Node node1 = new Node(1, "张三", "第一");
        Node node2 = new Node(2, "李四", "第二");
        Node node3 = new Node(3, "王五", "第三");
        SignalLinkedList List = new SignalLinkedList();
        List.addNode(node1);
        List.addNode(node2);
        List.addNode(node3);
        System.out.println("尾插法插入节点后的链表：");
        List.showLinkedList();

        //按照no大小插入节点
        Node orderNode1 = new Node(6, "水浒", "第六");
        Node orderNode2 = new Node(5, "西游记", "第五");
        Node orderNode3 = new Node(4, "三国", "第四");
        List.addOrderNode(orderNode1);
        List.addOrderNode(orderNode2);
        List.addOrderNode(orderNode3);
        System.out.println("按no顺序插入节点后的链表：");
        List.showLinkedList();

        //修改节点的no值和修改后的内容
        List.changeNode(9, "红楼梦", "第七");
        //查看修改后的链表
        System.out.println("修改后的链表为：");
        List.showLinkedList();

        //删除某节点
        List.del(5);
        //查看删除后的链表
        System.out.println("删除后的链表为：");
        List.showLinkedList();

        //链表中有效节点的个数
        System.out.println("链表中有效节点的个数:");
        System.out.println(List.nodeNum());

        //查找单链表中的倒数第k个节点
        Node kNode = List.reciprocalKNode(1);
        System.out.println("单链表中的倒数第k个节点的信息为：");
        System.out.printf("no = %d name = %s nickName = %s\n", kNode.no, kNode.name, kNode.nickName);

        //单链表的反转
        System.out.println("反转后的单链表为：");
        List.reverseLinkedList(List);
        List.showLinkedList();
    }
}
复制代码