[数据结构与算法]单向链表：排序、不排序

?* 链表：
?* ? ? ?1.链表是以节点的方式来存储数据的
?* ? ? ?2.每个节点含data域，next域：指向下一个节点
?* ? ? ?3.链表的内存布局不一定连续，依据需求
?* ? ? ?4.链表分为：带头节点、不带头节点

/**
 * 链表：
 *      1.链表是以节点的方式来存储数据的
 *      2.每个节点含data域，next域：指向下一个节点
 *      3.链表的内存布局不一定是连续的
 *      4.链表分为：带头节点、不带头节点
 *
 * 实现单项链表且带有头节点：add()不考虑排序，sortAdd()考虑排序进行插入
 *      1.头节点：不存储数据，代表单链表的头
 *      2.尾节点：下一个节点指向为null
 *
 * 注：
 *         a.链表操作中多个引用指向但是操作的对象是同一个，为了防止当前指针后移
 *     更新节点next指向后导致链表断开的问题，使用一个辅助指针指向当前节点的
 *     下一个节点，以牵住后续节点。
 *         b.链表有序合并时，思路：遍历要合并的链表，对于其单一节点使用orderAdd()
 *     方法即可，但前提要保存下一次要操作的节点，所以需要一个辅助指针next牵住
 */
package com.kali.structure.linked_1;

import java.util.Stack;

public class TestLink {
    public static void main(String[] args) {
        Link link = new Link();
        link.orderAdd(new Node(1,"松江","及时雨"));
        link.orderAdd(new Node(7,"林冲","豹子头"));
        link.orderAdd(new Node(17,"林冲","豹子头"));
        link.orderAdd(new Node(77,"林冲","豹子头"));
        link.orderAdd(new Node(5,"林冲","豹子头"));
        Link link2 = new Link();
        link2.orderAdd(new Node(1,"吴用","智多星"));
        link2.orderAdd(new Node(3,"卢俊义","玉麒麟"));
        link2.orderAdd(new Node(6,"卢俊义","玉麒麟"));

        System.out.println("link1");
        link.showLink();
        System.out.println("link2");
        link2.showLink();
        /*link.update(new Node(7,"义","麒麟"));
        System.out.println("更新后");
        link.showLink();
        System.out.println("删除后");
        link.delete(4);
        link.showLink();
        System.out.println("链表有效节点 " + link.length() + " 个");
        link.getK(4);*/
        /*System.out.println("反转后");
        link.reverse();
        link.showLink();
        System.out.println("反转打印");
        link.reversePrint();*/
        System.out.println("合并链表");
        link.mergeLink(link2);
        link.showLink();
    }
}

class Link{
    private Node head;

    public Link() {
        this.head = new Node();
    }

     /*
        合并两个有序链表，合并之后依然有序，不能有重复元素
     */
    public void mergeLink(Link tar){
        if(tar.head.next == null || head.next == null){
            System.out.println("链表为空");
            return;
        }

        Node index = tar.head.next;
        Node next;//记录链表的下一个节点备用
        while (index != null) {
            next = index.next;
            orderAdd(index);
            index = next;
        }

    }

    /*
     * 1.逆序打印链表，如果先反转导致链表结构变化
     * 2.使用栈结构，将节点压入栈，利用栈的先进后出特点实现逆序打印
     */
    public void reversePrint(){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        Node index = head.next;
        //创建一个栈
        Stack<Node> stack = new Stack<>();
        while (index != null){
            stack.push(index);
            index = index.next;
        }

        while(stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

    /*链表反转*/
    public void reverse(){
        if(head.next == null || head.next.next == null){
            System.out.println("链表为空或者只有一个节点");
            return;
        }

        Node index = head.next;//辅助新链表构成的指针
        Node next;//指向当前节点的下一个节点
        Node rev = new Node();
        //遍历原链表，每遍历一个节点就取出一个，并放在新的链表的最前端
        while(index != null){
            next = index.next;//保存下一个节点
            index.next = rev.next;//将rev.next后的牵在index后
            rev.next = index;//牵好的index由rev指向
            index = next;
        }

        head.next = rev.next;
    }

     /*
        查找单链表倒数第k个元素
            1.获取链表总长度length
            2.然后遍历到length-k位置就可拿到
     */
    public void getK(int k){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        
        //校验k值
        if(k > length() || k <= 0){
            System.out.println("链表越界，只有" + length() + "个元素，没有倒数第" + k + "个");
            return;
        }
        
        int count = 0;
        Node index = head;
        while(count <= (length() - k)){
            index = index.next;
            count ++;
        }

        System.out.println(index);
    }


    /*获取链表有效长度*/
    public int length(){
        Node index = head.next;
        
        if(head.next == null){
            return 0;
        }
        
        int length = 0;
        while (index != null){
            length ++;
            index = index.next;
        }
        return length;
    }


    /*删除节点，核心：没有引用指向的节点认为其删除*/
    public void delete(int id){
        if(head.next == null){
            System.out.println("链表为空，不能删除该节点");
            return;
        }

        Node index = head;
        boolean flag = false;
        while(true){
            if(index.next == null){
                break;
            }
            if(index.next.id == id){
                flag = true;
                break;
            }
            index = index.next;
        }

        if(flag){
            index.next = index.next.next;
        }else{
            System.out.println("没有找到要删除的节点，序号为 " + id);
        }
    }


    /*更新节点*/
    public void update(Node node){
        if(head.next == null){
            System.out.println("链表为空，不能更新");
            return;
        }

        Node index = head.next;
        boolean flag = false;
        while(true){
            if(index == null){
                break;
            }
            if(index.id == node.id){
                flag = true;
                break;
            }

            index = index.next;
        }

        if(flag){
            index.name = node.name;
            index.alias = node.alias;
        }else{
            System.out.println("没有查找到该元素，序号为 " + node.id);
        }
    }

    /*考虑排序的节点插入：找到位置插入节点，修改前后指针的指向*/
    public void orderAdd(Node node){
        Node index = head;
        //是否有重id的标识
        boolean flag = false;
        //找到插入点
        while(true){
            if(index.next == null){
                break;
            }
            if(index.next.id > node.id){
                break;
            }else if(index.next.id == node.id){
                flag = true;
                break;
            }
            index = index.next;
        }

        if(flag){
            System.out.println("元素已存在，序号为 " + node.id);
        }else{
            node.next = index.next;
            index.next = node;
        }
    }

    /*添加元素到尾部*/
    public void add(Node node){
        Node index = head;
        //遍历到链表尾部，添加元素
        while (index.next != null) {
            index = index.next;
        }

        index.next = node;
    }

    /*遍历并输出所有节点*/
    public void showNodes(){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        Node index = head.next;
        while (index != null) {

            System.out.println(index);

            index = index.next;
        }
    }
}

class Node{
    public int id;
    public String name;
    public String alias;
    public Node next;

    public Node() {
    }

    public Node(int id, String name, String alias) {
        this.id = id;
        this.name = name;
        this.alias = alias;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", alias='" + alias + '\'' +
                '}';
    }
}