LeetCode算法练习top100：（4）链表

￡神魔★判官ぃ 2024-02-18 11:13 28阅读 0赞

package top100.top链表;
    
    import top100.ListNode;
    import top100.Node;
    
    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.HashMap;
    
    public class TOP {
        
        //160. 相交链表
        //hashmap方法太low了
        //判断链表是否相交
        //双指针遍历两个相交链表,如果有相遇点，路径节点数一定相同
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            if (headA == null || headB == null) {
        
                return null;
            }
            ListNode cur1 = headA, cur2 = headB;
            while (cur1 != cur2) {
         //如果相交，则一定会有cur1 = cur2，如果不相交，cur1 = cur2 = null
                cur1 = cur1 == null ? headB : cur1.next;
                cur2 = cur2 == null ? headA : cur2.next;
            }
            return cur1;
        }
    
        //206. 反转链表
        public ListNode reverseList(ListNode head) {
        
            if (head == null) return null;
            ListNode pre = null, cur = head;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    
        //234. 回文链表
        //方法很多，反转链表，或者取出数据再判断
        public boolean isPalindrome(ListNode head) {
        
            if (head == null) {
        
                return true;
            }
            ArrayList<Integer> list = new ArrayList<>();
            while (head != null) {
        
                list.add(head.val);
                head = head.next;
            }
            for (int i = 0; i < list.size() / 2; i++) {
        
                int a = list.get(i);
                int b = list.get(list.size() - 1 - i);
                if (a != b) {
        
                    return false;
                }
            }
            return true;
        }
        //反转链表的前一半再同时便利两部分
        public boolean isPalindrome(ListNode head) {
        
            if(head == null || head.next == null) return false;
            ListNode pre = null;
            ListNode slow = head, fast = head;
            //遍历的时候同时反转，很妙
            while(fast != null && fast.next != null){
        
                // 快指针每次前进两步
                fast = fast.next.next;
                // 每次循环将局部链表反转
                ListNode tmp = slow.next;
                slow.next = pre;
                pre = slow;
                slow = tmp;
            }
            // 1.偶数链表循环结束后，fast == null，
            // pre指向前半部分第一个回文数，slow指向后半部分第一个回文数
            // 2. 奇数链表循环结束后，fast !=null, fast.next == null
            // pre指向前半部分第一个回文数，slow指向后半部分第一个链表。
            // 要将slow向前推进一步
            if(fast != null) slow = slow.next;
            // 此时pre指向前半部分第一个回文数，slow指向后半部分第一个回文数
            while (pre != null || slow != null){
        
                if(pre.val != slow.val) return false;
                pre = pre.next;
                slow = slow.next;
            }
            return true;
        }
    
        //141. 环形链表
        //链表是否有环：快慢指针，如果有环，肯定会相遇
        public boolean hasCycle(ListNode head) {
        
            if (head == null) {
        
                return false;
            }
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
        
                    return true;
                }
            }
            return false;
        }
    
        //142. 环形链表 II
        //链表的环：hashmap 或者 双指针
        public ListNode detectCycle(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
         //遇到环，快指针重新走
                    fast = head;
                    while (fast != slow) {
        
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    
        //21. 合并两个有序链表
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
            if (list1 == null) {
        
                return list2;
            }
            if (list2 == null) {
        
                return list1;
            }
            ListNode temp = new ListNode(-1);
            ListNode cur = temp;
            while (list1 != null && list2 != null) {
        
                if (list1.val < list2.val) {
        
                    cur.next = list1;
                    list1 = list1.next;
                } else {
        
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            if (list1 != null) {
        
                cur.next = list1;
            }
            if (list2 != null) {
        
                cur.next = list2;
            }
            return temp.next;
        }
    
    
        //2. 两数相加
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            int carry = 0;
    
            ListNode fake = new ListNode(-1);
            ListNode pre = fake;
    
            while(l1 != null || l2 != null || carry != 0) {
        
                int num1 = l1 == null ? 0 : l1.val;
                int num2 = l2 == null ? 0 : l2.val;
    
                ListNode cur = new ListNode((num1 + num2 + carry) % 10);
                pre.next = cur;
                pre = cur;
    
                carry = (num1 + num2 + carry) / 10;
    
                l1 = l1 == null ? null : l1.next;
                l2 = l2 == null ? null : l2.next;
            }
    
            pre.next = null;
            return fake.next;
        }
    
        //19. 删除链表的倒数第 N 个结点
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            //双指针
            ListNode slow = head;
            ListNode fast = head;
            //fast先移动n个，再同时移动fast和slow,使fast在最后一个结点，则slow就是倒数第n个
            for (int i = 0; i < n; i++) {
        
                fast = fast.next;
            }
            ListNode pre = dummy;
            while (fast != null) {
        
                pre = slow;
                slow = slow.next;
                fast = fast.next;
            }
            pre.next = slow.next;
            return dummy.next;
        }
    
        //24. 两两交换链表中的节点
        //用了k个一组反转链表的方法
        public ListNode swapPairs(ListNode head) {
        
            if (head == null) return null;
            if (head.next == null) return head;
    
            ListNode dummy = head.next;
            ListNode next = dummy.next;
            //翻转
            dummy.next = head;
            head.next = swapPairs(next);
            return dummy;
        }
    
        //25. K 个一组翻转链表
        public ListNode reverseKGroup(ListNode head, int k) {
        
            if (head == null) return null;
            //计算结点是否有k个
            ListNode cur = head;
            for (int i = 0; i < k; i++) {
        
                if (cur == null) {
        
                    return head;
                }
                cur = cur.next;
            }
            //翻转k个节点
            ListNode pre = null;
            cur = head;
            int count = 1;
            while (count <= k) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
                count++;
            }
            //拼接
            head.next = reverseKGroup(cur, k);
            return pre;
        }
    
        //138. 随机链表的复制
        public Node copyRandomList(Node head) {
        
            if (head == null) {
        
                return null;
            }
            //HashMap记录两个链表的对应情况
            HashMap<Node, Node> map = new HashMap<>();
            Node cur = head;
            while (cur != null) {
        
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
        
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
        }
    
        //148. 排序链表
        //链表的归并排序
        public ListNode sortList(ListNode head) {
        
            if (head == null || head.next == null) return head;
            //链表分割为两部分：快慢双指针
            //如果链表是偶数， 则需要找到中间节点的第一个
            //如果是找到链表中间节点的第二个，则可以去掉fast.next.next条件
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode temp = slow.next;//slow就是中间节点的第一个
            slow.next = null; //断开链表
            //递归排序两个链表
            ListNode left = sortList(head);
            ListNode right = sortList(temp);
            //合并排序后的链表
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            while (left != null && right != null) {
        
                if (left.val < right.val) {
        
                    cur.next = left;
                    left = left.next;
                } else {
        
                    cur.next = right;
                    right = right.next;
                }
                cur = cur.next;
            }
            //剩余部分添加到后面
            cur.next = left != null ? left : right;
            return dummy.next;
        }
    
        //23. 合并 K 个升序链表
        //归并排序链表数组，最终实现两两合并链表
        public ListNode mergeKLists(ListNode[] lists) {
        
            if (lists.length == 0) return null;
            return mergeKLists(lists, 0, lists.length - 1);
        }
        private ListNode mergeKLists(ListNode[] lists, int left, int right) {
        
            //只有一个链表时，有序，返回该列表的头节点
            if (left == right) return lists[left];
            //递归
            int mid = left + (right - left) / 2;
            ListNode node1 = mergeKLists(lists, left, mid);
            ListNode node2 = mergeKLists(lists, mid + 1, right);
            //合并
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            while (node1 != null && node2 != null) {
        
                if (node1.val < node2.val) {
        
                    cur.next = node1;
                    node1 = node1.next;
                } else {
        
                    cur.next = node2;
                    node2 = node2.next;
                }
                cur = cur.next;
            }
            cur.next = node1 == null ? node2 : node1;
            return dummy.next;
        }
    
        //146. LRU 缓存
        class LRUCache {
        
            //需要一个hashmap记录数据
            //需要对key值按照使用的顺序排序：双向链表，队列等
            int capacity;
            HashMap<Integer, Integer> map;
            ArrayDeque<Integer> deque; //最近使用的数据放在队首
            public LRUCache(int capacity) {
        
                this.capacity = capacity;
                this.map = new HashMap<>();
                this.deque = new ArrayDeque<>();
            }
    
            public int get(int key) {
        
                if (map.containsKey(key)) {
        
                    //最近使用了数据，放到队首
                    deque.remove(key);
                    deque.offerFirst(key);
                    return map.get(key);
                } else {
        
                    return -1;
                }
            }
    
            public void put(int key, int value) {
        
                if (map.containsKey(key)) {
        
                    map.put(key, value);
                    deque.remove(key);
                } else {
        
                    if (map.size() == capacity) {
        
                        //新加入数据导致超出容量，删除队尾的数据
                        map.remove(deque.pollLast());
                    }
                    map.put(key, value);
                }
                //新加入的数据或者更新的数据都放在队首
                deque.offerFirst(key);
            }
        }
    }