单链表的学习心得

你的名字 2023-07-07 03:50 10阅读 0赞

package com.yg.linkedList;/*
    @author  Ge
    @date    2020/2/19  15:01
    */
    
    import javax.validation.constraints.Pattern;
    import java.util.Stack;
    
    public class SingleLinkedListDemo {
        public static void main(String[] args) {
            SingleLinkedList linkedList1 = new SingleLinkedList();
    //        linkedList1.addNode(new HereNode(1,"宋江","及时雨"));
    //        linkedList1.addNode(new HereNode(2,"卢俊义","玉麒麟"));
    //        linkedList1.addNode(new HereNode(3,"吴用","智多星"));
    //        linkedList1.addNode(new HereNode(4,"林聪","豹子头"));
            //按照编号加入
            linkedList1.addByNo(new HereNode(1, "宋江", "及时雨"));
            linkedList1.addByNo(new HereNode(3, "吴用", "智多星"));
            linkedList1.addByNo(new HereNode(2, "卢俊义", "玉麒麟"));
            linkedList1.addByNo(new HereNode(4, "林聪", "豹子头"));
            HereNode head = linkedList1.getHead();
    //        linkedList1.addByNo(new HereNode(4, "aaa", "fff"));
    //       SingleLinkedList.showHereNode(head);
    //        System.out.println("*****************************************");
            //修改节点信息
    //        linkedList1.updataNode(new HereNode(5, "小卢", "玉麒麟--"));
    //       SingleLinkedList.showHereNode(head);
            //删除节点信息
    //        linkedList1.delNodeByNo(4);
    //        linkedList1.delNodeByNo(1);
    //        linkedList1.delNodeByNo(2);
    //        linkedList1.delNodeByNo(3);
    //        System.out.println("删除后");
    //       SingleLinkedList.showHereNode(head);
            //获取链表节点个数
    //        int length=SingleLinkedList.getLength(linkedList1.getHead());
    //        System.out.println("链表节点个数为:" +length);
            //得到链表倒数第index个节点
    //        int index = 2;
    //        System.out.println(SingleLinkedList.findLastIndexNode(head, index));
            //链表反转
    //        System.out.println("反转前****");
    //          SingleLinkedList.showHereNode(head);
    //       SingleLinkedList.getReverseHead(head);
    //        System.out.println("反转后****");
    //       SingleLinkedList.showHereNode(head;
    
            //反向打印链表
    //        SingleLinkedList.reversePrint(head);
    
            //合并有序链表
            SingleLinkedList linkedList2 = new SingleLinkedList();
            linkedList2.addNode(new HereNode(1,"小宋","及时雨"));
            linkedList2.addNode(new HereNode(5,"小卢","玉麒麟"));
            linkedList2.addNode(new HereNode(7,"小吴","智多星"));
            linkedList2.addNode(new HereNode(6,"小林","豹子头"));
            HereNode head2=linkedList2.getHead();
            SingleLinkedList.showHereNode(SingleLinkedList.mergeTwoLists(head,head2));
    
        }
    }
    
    class SingleLinkedList {
        private HereNode head = new HereNode(0, "", "");
    
        public HereNode getHead() {
            return head;
        }
    
        //添加节点
        public void addNode(HereNode node) {
            HereNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }
    
        //按照编号加入
        public void addByNo(HereNode node) {
            boolean flag = false;
            HereNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.no > node.no) {
                    break;
                } else if (temp.next.no == node.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag == true) {
                System.out.println("添加失败编号为:" + node.no + "已经存在!!");
            } else {
                node.next = temp.next;
                temp.next = node;
            }
    
        }
    
        //修改链表节点信息
        public void updataNode(HereNode newNode) {
            boolean flag = false;
            if (head.next == null) {
                System.out.println("列表为空!!");
                return;
            }
            HereNode temp = head.next;
            while (true) {
                if (temp == null) {
                    break;
                } else if (temp.no == newNode.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                temp.name = newNode.name;
                temp.nickName = newNode.nickName;
            } else {
                System.out.println("该节点不存在!!");
            }
        }
    
        //删除节点
        public void delNodeByNo(int no) {
            boolean falg = false;
            if (head.next == null) {
                return;
            }
            HereNode temp = head;
            while (true) {
                if (temp.next == null) {
                    System.out.println("节点为空!!");
                    break;
                }
                if (temp.next.no == no) {
                    falg = true;
                    break;
                }
                temp = temp.next;
    
            }
            if (falg) {
                temp.next = temp.next.next;
            } else {
                System.out.println("要删除的节点不存在!!");
            }
        }
    
    
        //显示节点(遍历)
        public  static void showHereNode(HereNode head) {
            if (head.next == null) {
                System.out.println("链表为空!!");
                return;
            }
            HereNode temp = head;
            while (true) {
    
                if (temp.next == null) {
                    return;
                }
                System.out.println(temp.next);
                temp = temp.next;
    
            }
        }
    
    
        //得到链表的节点个数
        public static int getLength(HereNode head) {
            int length = 0;
            if (head.next == null) {
                return 0;
            }
            HereNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                length++;
                temp = temp.next;
    
            }
            return length;
        }
    
        //得到链表倒数第index个节点
        //只要遍历(length-index)次就可以找到目标节点
        public static HereNode findLastIndexNode(HereNode head, int index) {
            //如果链表为空返回null
            if (head.next == null) {
                return null;//没有找到
            }
            //得到链表长度
            int length = getLength(head);
            //对index进行数据校验
            if (index <= 0 || index > length) {
                return null;
            }
            HereNode temp = head.next;
            for (int i = 0; i < length - index; i++) {
                temp = temp.next;
            }
            return temp;
    
        }
    
        //链表反转
        //1.定义一个新的头结点reverseHead
        //2.从头到尾的遍历原头结点,遍历一个就拆下来一个放到新头结点后面
        //3.将head.next=reverseHead.next;
        public static void getReverseHead(HereNode head) {
            if (head.next == null || head.next.next == null) {
                return;
            }
            HereNode reverseHead = new HereNode(0, "", "");
            //遍历原来链表
            HereNode cur = head.next;
            //指向当前节点[cur]的下一个节点
            HereNode next = null;
            while (cur != null) {
                next = cur.next;
                cur.next = reverseHead.next;
                reverseHead.next = cur;
                cur = next;
            }
            head.next = reverseHead.next;
    
    
        }
    
        //反向打印链表
        public static void reversePrint(HereNode head) {
            if (head.next == null) {
                return;
            }
            Stack<HereNode> stack = new Stack<>();
            HereNode temp = head.next;
            while (temp != null) {
                stack.push(temp);
                temp = temp.next;
            }
            while (stack.size() > 0) {
                System.out.println(stack.pop());
            }
        }
    
        //合并两个有序链表
        public static HereNode mergeTwoLists(HereNode l1, HereNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    
            HereNode head = null;
            if (l1.no <= l2.no){
                head = l1;
                head.next = mergeTwoLists(l1.next, l2);
            } else {
                head = l2;
                head.next = mergeTwoLists(l1, l2.next);
            }
            return head;
        }
    
    
    
    }
    
    class HereNode {
        public int no;
        public String name;
        public String nickName;
        public HereNode next;
    
        public HereNode(int no, String name, String nickName) {
            this.no = no;
            this.name = name;
            this.nickName = nickName;
            this.next = next;
        }
    
        @Override
        public String toString() {
            return "HereNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickName='" + nickName + '\'' +
                    '}';
        }
    }