【数据结构与算法】四、链表相关算法题

布满荆棘的人生 2023-10-09 14:28 12阅读 0赞

上一篇[【数据结构与算法】四、数组相关算法题][Link 1]

数据结构链表的实现思路和方式

#### 文章目录 ####

*  0、单项链表实现
 *  1、反转一个单向链表
 *  2、判断一个链表中是否有环
 *  3、 两两交换链表中的节点
 *  4、 有效的括号

## 0、单项链表实现 ##

/**
     * 单向链表实现
     */
    public class LinkedListForAlgorithm<E> {
        
        
        private Node<E> first;
    
        private Node<E> last;
    
        private int     size;
        
        
        /**
         * 一个私有的静态内部类作为链表的元素
         * 这里由于后面的算法题中需要使用到这个
         * 静态内部类，所以把其写成public的，并
         * 把其成员变量也写成public的
         * @author Peter
         */
        public static class Node<E>{
        
            
            public Node<E>  next;
            
            public  E item;
            
            public Node(){
        
                
            }
            
            public Node(E e){
        
                this.item=e;
            }
            
             @Override
             public String toString() {
        
                 if (item == null) {
        
                     return "null";
                 }
                 return item.toString();
             }
            
        }
        
        public void add(E e){
        
            Node<E> toAddNode=new Node<E>(e);
            //如果第一个为null证明现在是在添加第一个元素
            if(first==null && last==null){
        
                //那么就将第一个元素设为这个添加的元素
                first=toAddNode;
                //将末尾元素设为这个添加的元素
                last=toAddNode;
                this.size++;
                return;
            }
            //原有的last的下一个设置为本个
            last.next=toAddNode;
            //然后把现在的last设置为本个
            last=toAddNode;
            this.size++;
        }
        
        public boolean contains(E e) {
        
            //从第一个开始往下一个一个找，所以慢
            Node<E> current = first;
            while (current != null) {
        
                if (current.item.equals(e)) {
        
                    return true;
                }
                //没找到就往下继续找
                current = current.next;
            }
            /*
             * 如果都到最后一个元素了（末尾元素为null了）
             * 还是没找到，那么就返回不包含。
             */
            return false;
        }
        
        public E remove(){
        
            if(this.first==null||this.size==0){
        
                throw new RuntimeException("集合为空，不能在删除元素！");
            }
            Node<E> toRemoveNode=first;
            first=toRemoveNode.next;
            size--;
            return toRemoveNode.item;
        }
        
        
        public boolean remove(E e) {
        
            //第一个元素如果为null说明集合为空抛异常
            if (this.first == null || this.size == 0) {
        
                throw new RuntimeException("集合为空！");
            }
            Node<E> current = first;
            while (current!=null) {
        
                Node<E> toRemoveNode = current.next;
                /*
                 * 要删除的元素为第一个元素
                 * 那么将第一个元素删除
                 */
                if(current.item.equals(e)){
        
                    remove();
                    return true;
                }
                /*
                 * 如果要删除的元素为null，
                 * 证明集合中不包含要删除的元素，
                 * 直接跳出循环返回false
                 */
                if(toRemoveNode==null){
        
                    break;
                }
                /*
                 * 找到要删除元素的上一个元素
                 * 要删除元素的上一个元素为：current
                 * 要删除元素为：current.next
                 */
                if (toRemoveNode.item.equals(e)) {
        
                    //执行删除操作
                    current.next = toRemoveNode.next;
                    toRemoveNode.next = null;
                    toRemoveNode.item = null;
                    toRemoveNode = null;
                    this.size--;
                    return true;
                }
                //没找到就往下继续找
                current = current.next;
            }
            /*
             * 如果都到最后一个元素了（末尾元素为null了）
             * 还是没找到，那么就返回false，表示删除失败！。
             */
            return false;
        }
        
        
        public Node<E> getFirst() {
        
    		return first;
    	}
        
    	public void setFirst(Node<E> first) {
        
    		this.first = first;
    	}
    	
    	public Node<E> getLast() {
        
    		return last;
    	}
    
    	public void setLast(Node<E> last) {
        
    		this.last = last;
    	}
    
    	public int getSize() {
        
            return size;
        }
        
        
        @Override
        public String toString() {
        
            if (this.first == null || this.size == 0) {
        
                return "[]";
            }
            String toStr = "[";
            Node<E> current = first;
            while (current!= null) {
        
                toStr =  toStr+current.toString()+",";
                current = current.next;
            }
            return toStr.substring(0,toStr.length()-1)+"]" ;
        }
    
    	public static void main(String[] args) {
        
    	}
    }

## 1、反转一个单向链表 ##

/**
     * 力扣第206题：
     * https://leetcode-cn.com/problems/reverse-linked-list/
     * 在不使用其它数据结构的情况下
     * 反转一个单向链表
    
     */
    public class ReverseLinkedList {
        
    
    	public static void main(String[] args) {
        
    	    
    	    
    	    
    		//创建测试数据
    		LinkedListForAlgorithm<Integer> linkedList = new LinkedListForAlgorithm<>();
    	    linkedList.add(1);
    	    linkedList.add(2);
    	    linkedList.add(3);
    	    linkedList.add(4);
    	    linkedList.add(5);
    	    
    	    System.out.println("反转前的数据为："+linkedList);
    	    
    	    Node<Integer> first = linkedList.getFirst();
    	    
    	    
    //	    reverse1(first);
    	    reverse2(first);
    	    
    	    /*
    	     * 进行反转后因为链表内部的头指针和为指针还是原来的值
    	     * 所以需要进行设置正确
    	     */
    	    linkedList.setFirst(linkedList.getLast());
    	    linkedList.setLast(linkedList.getFirst());
    	    
    	    System.out.println("反转后的数据为："+linkedList);
    
    	}
    
        /**
         * 使用迭代的方式反转
         * 时间复杂度是：O(n)
         * 空间复杂度是：O(1)
         * @param first     链表中的头元素
         * @return  反转之后的头元素
         */
        private static <E> Node<E> reverse2(Node<E> first) {
        
            
            Node<E> newNode = null;
            
            while (first != null) {
        
                //先保存头节点的下一个，方便后续将头节点进行后移
                Node<E> next = first.next;
                //将头节点的下一个设置为新节点
                first.next = newNode;
                //修改新节点的指向老的节点
                newNode = first;
                //将头节点往后移
                first = next;
            }
            //返回反转之后的头节点
            return newNode;
            
            
        }
    
        /**
         * 使用递归的方式反转
         * 思路：假设除了头元素的后面所有元素都是已经反转好的，
         * 那么现在只需要将头元素的下一个即（已经反转好的那一部分的尾部）
         * 的下一个指向头元素后再将头元素的下一个指向null即可。
         * 
         * 时间复杂度是：O(n)
         * 空间复杂度因为使用了递归，而递归使用了隐式地栈，
         * 所以就是O(n)
         * @param first     链表中的头元素
         * @return  反转之后的头元素
         */
        private static <E> Node<E> reverse1(Node<E> first) {
        
            
            //最外层的方法是处理的第1个元素
            if(first == null || first.next == null){
        
                return first;
            }
            
            //处理第2个元素以及其后的元素
            Node<E> reversedNode = reverse1(first.next);
            
            first.next.next = first;
            first.next = null;
            
            return reversedNode;
        }
    
    }

## 2、判断一个链表中是否有环 ##

/**
     * 力扣第141题：
     * https://leetcode-cn.com/problems/linked-list-cycle/
     * 
     * 判断一个链表中是否有环
     */
    public class LeetCodeTest02 {
        
    
    	public static void main(String[] args) {
        
    		//准备数据
    	    Node<Integer> first = new Node<>(3);
    	    Node<Integer> node1 = new Node<>(2);
    	    Node<Integer> node2 = new Node<>(0);
    	    Node<Integer> node3 = new Node<>(-4);
    	    
    	    
    	    first.next = node1;
    	    node1.next = node2;
    	    node2.next = node3;
    	    node3.next = node1;
    	    
    //	    node3.next = null;
    	    
    	    System.out.println("是否有环？"+hasCycle1(first));
    //	    System.out.println("是否有环？"+hasCycle2(first));
    	    
    
    	}
    	
    	
    	/**
    	 * 使用暴力方式
    	 * 时间复杂度为：O(n)
    	 * 因为使用了额外的数组空间所以
    	 * 空间复杂度为：O(n)
    	 * @param first    链表中的头元素
    	 * @return     是否有环
    	 */
    	public static <E> boolean hasCycle1(Node<E> first) {
        
    	    //校验入参防止空指针
    	    if(first == null || first.next == null){
        
    	        return false;
    	    }
            
    	    //创建一个Set去存放已经遍历过的节点
    	    Set<Node<E>> resultSet = new HashSet<>();
    	    //遍历链表的每一个元素
    	    while(first.next !=null){
        
    	        //如果Set中不存在就将其添加进Set中后跳过本次循环
    	        if(resultSet.contains(first)){
        
    	        	//如果Set中存在就直接返回true表示有环
    	        	return true;
    	        }
    	        resultSet.add(first);
    	        //然后first的指针往后移
    	        first = first.next;
    	    }
    	    //如果到了这里说明遍历完毕没有环就返回false
    	    return false;
        }
    	
    	
    	/**
         * 使用快慢指针方式
         * 原理：如果有环，那么快指针和慢指针都最终会进入
         * 环中，那么总有一天快指针会套圈慢指针
         * 时间复杂度为：O(n)
         * 空间复杂度为：O(1)
         * @param first    链表中的头元素
         * @return     是否有环
         */
        public static <E> boolean hasCycle2(Node<E> first) {
        
            //校验入参防止空指针
            if(first == null || first.next == null){
        
                return false;
            }
            
            Node<E> slow = first;
            Node<E> fast = first;
            
            /*
             * 开始遍历，快指针每次走两步，慢指针每次走一步
             * 如果快指针不为null且快指针的下一个不为null
             * 说明快指针还没有到达终点就继续循环
             */
            while(fast != null && fast.next != null){
        
                //慢指针走一步
                slow = slow.next;
                //快指针走两步
                fast = fast.next.next;
                //如果快指针和慢指针相等说明快指针已经套圈慢指针所以返回true
                if(slow == fast){
        
                    return true;
                }
            }
            //如果到了这里说明遍历完毕快指针已经到达终点所以没有环就返回false
            return false;
        }
    	
    
    }

## 3、 两两交换链表中的节点 ##

/**
     * 力扣第24题：
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 两两交换链表中的节点
     */
    public class LeetCodeTest01 {
        
    
    	public static void main(String[] args) {
        
    	    //创建测试数据
            LinkedListForAlgorithm<Integer> linkedList = new LinkedListForAlgorithm<>();
            linkedList.add(1);
            linkedList.add(2);
            linkedList.add(3);
            linkedList.add(4);
    //        linkedList.add(5);
            
            System.out.println("处理前的数据为："+linkedList);
            
            Node<Integer> first = linkedList.getFirst();
            
    //        Node<Integer> resultFirst = swapPairs1(first);
            Node<Integer> resultFirst = swapPairs2(first);
            
            /*
             * 进行反转后因为链表内部的头指针和尾指针还是原来的值
             * 所以需要进行设置正确，否则会导致toString方法混乱
             */
            linkedList.setFirst(resultFirst);
            
            System.out.println("处理后的数据为："+linkedList);
    	}
    
        /**
         * 递归的方式实现
         * 
         * 时间复杂度为：O(n)
         * 由于使用了递归存在隐式的栈空间，所以
         * 空间复杂度为：O(n)
         * @param first 链表中的头元素
         * @return 处理之后的头节点
         */
        private static <E> Node<E> swapPairs1(Node<E> first) {
        
            
            /*
             * 递归的终止条件：
             *      如果链表长度为奇数则是first.next == null
             *      例如：链表为：1-->2-->3，first = 1 时
             *      如果链表长度为偶数则是first == null
             *      例如：链表为：3-->4，first = 3 时
             */
            if(first == null || first.next == null) {
        
                return first;
            }
            /*
             * 假设链表是 1->2->3->4
             * 那么就先保存节点2
             */
            Node<E> tmp = first.next;
            /*
             * 开始递归，处理节点3->4
             * 当递归结束返回后，就变成了4->3
             * 此时first的下一个就指向了4，变成1->4->3
             */
            first.next = swapPairs1(tmp.next);
            //再将2节点指向节点1即可
            tmp.next = first;
            return tmp;
            
        }
        
        /**
         * 迭代的方式实现
         * 
         * 时间复杂度为：O(n)
         * 空间复杂度为：O(1)
         * @param first 链表中的头元素
         * @return  处理之后的头节点
         */
        private static <E> Node<E> swapPairs2(Node<E> first) {
        
            //创建一个空节点去指向原有链表的头节点
            Node<E> firstPre = new Node<>();
            firstPre.next = first;
            
            //用一个变量去存需要替换的元素
            Node<E> tmp = firstPre;   
            //开始循环去两两交换指针
            while(tmp.next != null && tmp.next.next != null){
        
                //pre指向要交换的两个节点的前者
                Node<E> pre = tmp.next;
                //next指向要交换的两个节点的后者
                Node<E> next = tmp.next.next;
                
                //进行两两交换指向
                /*
                 * 将上一次循环保存的交换后的后者的下一个
                 * 指向其下一个的下一个，即：本次交换后的前者。
                 */
                tmp.next = next;
                //将前者的下一个指向后者的下一个
                pre.next = next.next;
                //将后者的下一个指向前者
                next.next = pre;
                //再保存原始的前者
                tmp = pre;
            }
            //返回空节点指向的节点即：新的头节点
            return firstPre.next;
        }
    
    }

## 4、 有效的括号 ##

/**
     * 力扣第20题：
     * https://leetcode-cn.com/problems/valid-parentheses/
     * 有效的括号
     */
    public class LeeCodeTest01 {
        
    
    	public static void main(String[] args) {
        
    		
    	    //准备数据
    //	    String str = "[](){}";
    //	    String str = "[(]){}";
    //	    String str = "[(){}]";
    //	    String str = "()))";
    	    String str = "()";
    	    
    	    
    	    System.out.println(str+"是一个合法的字符串么？"+isValid1(str));
    	    System.out.println(str+"是一个合法的字符串么？"+isValid2(str));
    	    
    
    	}
    	
    	/**
    	 * 暴力方式：
    	 * 用其中合法的括号去每次替换成空字符串，最后的得到的结果
    	 * 的长度如果为0，说明是合法的，否则不合法
    	 * 
    	 * 因为每次replace方法参数为大于1的字符串那么就是一个O(n)的操作，
    	 * 在加上外层的循环那么就是嵌套的一个循环的情况，所以
    	 * 时间复杂度为：O(n^2)
    	 * 空间复杂度为：O(1)
    	 * @param str  带有括号的字符串
    	 * @return     是否合法
    	 */
    	public static boolean isValid1(String str){
        
    	    
    	    //校验入参
    	    if(str == null || str.length() == 0){
        
    	        return false;
    	    }
    	    
    	    //如果长度不为偶数那么也不可能是合法的
    	    if((str.length() & 1) != 0){
        
    	        return false;
    	    }
    	    
    	    //首先保存一下要处理的字符串
    	    String tmp = str;
    	    
    	    //对其进行循环处理
    	    while(str.length() != 0){
        
    	        //每次循环对每一种合法括号进行替换
    	        str = str.replace("()", "");//(){[}]
    	        str = str.replace("[]", "");
    	        str = str.replace("{}", "");
    	        //替换完后，判断如果和原有的字符串相同则说明不合法直接返回false
    	        if(str.equals(tmp)){
        
    	            return false;
    	        }
    	        //否则说明有可能合法将要处理的字符串重新赋值后继续下一次循环
    	        tmp = str;
    	    }
    	    //如果循环结束那么就是处理后的字符串为空字符串，就说明其是合法的返回true
            return true;
    	}
    	
    	
    	/*
    	 * 声明一个装有所有合法括号的对应关系的Map
    	 */
    	private static final Map<Character, Character> BRACKETS_MAP = new HashMap<>();
    	
    	static {
        
    	    BRACKETS_MAP.put('(', ')');
    	    BRACKETS_MAP.put('[', ']');
    	    BRACKETS_MAP.put('{', '}');
    	}
    	
    	/**
         * 使用栈方式：
         * 
         * 
         * 时间复杂度为：O(n)
         * 空间复杂度为：O(n)
         * @param str  带有括号的字符串
         * @return     是否合法
         */
        public static boolean isValid2(String str){
        
            
            //校验入参
            if(str == null || str.length() == 0){
        
                return false;
            }
            
            //如果长度不为偶数那么也不可能是合法的
            if((str.length() & 1) != 0){
        
                return false;
            }
            
            //如果map中不包含第一个字符，说明没有括号存在，直接返回false
            if(!BRACKETS_MAP.containsKey(str.charAt(0))){
        
                return false;
            }
            //创建一个栈用于辅助寻找
            Stack<Character> stack = new Stack<>();
            
            //遍历字符串的字符数组    [(])
            for (Character ch : str.toCharArray()) {
        
                //如果为左括号，那么就执行入栈
                if(BRACKETS_MAP.containsKey(ch)){
        
                    stack.push(ch);
                    continue;
                }
                //如果为右括号，且此时栈大小为0，说明也不满足直接返回false
                if(stack.isEmpty()){
        
                    return false;
                }
                //如果为右括号，且此时栈大小不为0，那么就弹栈并比较如果不同直接返回false
                if(ch != BRACKETS_MAP.get(stack.pop())){
        
                    return false;
                }
                //如果相同那么继续下一次循环
                    
            }
            
            //如果最后栈大小依然为0，那么表示是合法的
            return stack.size() == 0;
        }
    
    }

[Link 1]: https://blog.csdn.net/weixin_43333483/article/details/125628888?spm=1001.2014.3001.5501