算法练习（5）：牛客在线编程01 链表

深藏阁楼爱情的钟 2023-10-14 16:18 7阅读 0赞

package jz.bm;
    
    import jz.ListNode;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.HashSet;
    
    public class bm1 {
        
        /**
         * BM1 反转链表
         */
        public ListNode ReverseList(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            ListNode pre = head;
            ListNode cur = head.next;
            pre.next = null;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    
        /**
         * BM2 链表内指定区间反转
         */
        public ListNode reverseBetween (ListNode head, int m, int n) {
        
            ListNode temp = new ListNode(-1);
            temp.next = head;
    
            int index = 1;
            ListNode mPre = temp;
            ListNode mNode = head;
            while (index < m) {
        
                mPre = mNode;
                mNode = mNode.next;
                index++;
            }
    
            ListNode nPre = null;
            ListNode nNode = mNode;
            while (index < n) {
        
                ListNode next = nNode.next;
                nNode.next = nPre;
                nPre = nNode;
                nNode = next;
                index++;
            }
    
            mPre.next = nPre;
            mNode.next = nNode;
    
            return temp.next;
        }
    
        /**
         * BM3 链表中的节点每k个一组翻转
         */
        public ListNode reverseKGroup (ListNode head, int k) {
        
            if(head == null) {
        
                return null;
            }
    
            int n = 1;
            ListNode cur = head;
            while (n <= k) {
        
                if(cur == null) {
        
                    return head;
                }
                cur = cur.next;
                n++;
            }
    
            ListNode pre = null;
            cur = head;
            n = 1;
            while (n <= k) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
                n++;
            }
            head.next = reverseKGroup(cur, k);
            return pre;
        }
    
        /**
         * BM4 合并两个排序的链表
         */
        public ListNode Merge(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;
            }
            while (list1 != null) {
        
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }
            while (list2 != null) {
        
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
            return temp.next;
        }
    
        /**
         * BM5 合并k个已排序的链表
         */
        public ListNode mergeKLists (ArrayList<ListNode> lists) {
        
            return divideMergeKLists(lists, 0, lists.size() - 1);
        }
    
        public ListNode divideMergeKLists (ArrayList<ListNode> lists, int left, int right) {
        
            if (left > right) {
        
                return null;
            } else if (left == right) {
         //只有一个链表，直接返回
                return lists.get(left);
            }
            int mid = (left + right) / 2;
            return Merge(divideMergeKLists(lists, left, mid), divideMergeKLists(lists, mid + 1, right));
        }
    
        /**
         * BM6 判断链表中是否有环
         */
        public boolean hasCycle(ListNode head) {
        
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if (fast == slow) {
        
                    return true;
                }
            }
            return true;
        }
    
        /**
         * BM7 链表中环的入口结点
         */
        public ListNode EntryNodeOfLoop(ListNode pHead) {
        
            //快慢指针
            ListNode slow = pHead;
            ListNode fast = pHead;
            while(fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                //有环，找到相遇点
                if (slow == fast) {
        
                    //两个指针同时走，相遇点就是环起始点
                    fast = pHead;
                    while(fast != null) {
        
                        if (slow == fast) {
        
                            return slow;
                        }
                        fast = fast.next;
                        slow = slow.next;
                    }
                }
            }
            return null;
        }
    
        /**
         * BM8 链表中倒数最后k个结点
         */
        public ListNode FindKthToTail (ListNode pHead, int k) {
        
            //双指针
            ListNode slow = pHead;
            ListNode fast = pHead;
            for (int i = 0; i < k; i++) {
        
                if (fast != null) {
        
                    fast = fast.next;
                } else {
        
                    return null;
                }
            }
            while (fast != null) {
        
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    
        /**
         * BM9 删除链表的倒数第n个节点
         */
        public ListNode removeNthFromEnd (ListNode head, int n) {
        
            ListNode temp = new ListNode(-1);
            temp.next = head;
            int len = 0;
            ListNode cur = head;
            while (cur != null) {
        
                len++;
                cur = cur.next;
            }
    
            ListNode pre = temp;
            cur = head;
            for (int i = 0; i < len; i++) {
        
                if(i == len - n) {
        
                    pre.next = cur.next;
                    break;
                } else {
        
                    pre = cur;
                    cur = cur.next;
                }
            }
            return temp.next;
        }
    
        /**
         * BM10 两个链表的第一个公共结点
         */
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        
            if (pHead1 == null) {
        
                return null;
            }
            if (pHead2 == null) {
        
                return null;
            }
            HashSet<ListNode> set = new HashSet<>();
            ListNode cur = pHead1;
            while (cur != null) {
        
                set.add(cur);
                cur = cur.next;
            }
            cur = pHead2;
            while (cur != null) {
        
                if (set.contains(cur)) {
        
                    return cur;
                }
                cur = cur.next;
            }
            return null;
        }
    
        /**
         * BM11 链表相加(二)
         */
        public ListNode addInList (ListNode head1, ListNode head2) {
        
            head1 = ReverseList(head1);
            head2 = ReverseList(head2);
            int temp = 0;
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            while (head1 != null || head2 != null || temp != 0) {
        
                int v1 = head1 == null ? 0 : head1.val;
                int v2 = head2 == null ? 0 : head2.val;
                cur.next = new ListNode((v1 + v2 + temp) % 10);
                temp = (v1 + v2 + temp) / 10;
                cur = cur.next;
                head1 = head1 == null ? null : head1.next;
                head2 = head2 == null ? null : head2.next;
            }
            return ReverseList(head.next);
        }
    
        /**
         * BM12 单链表的排序
         */
        public ListNode sortInList (ListNode head) {
        
            ArrayList<Integer> list = new ArrayList<>();
            ListNode cur = head;
            while (cur != null) {
        
                list.add(cur.val);
                cur = cur.next;
            }
            Collections.sort(list);
            cur = head;
            for (Integer integer : list) {
        
                cur.val = integer;
                cur = cur.next;
            }
            return head;
        }
    
        /**
         * BM13 判断一个链表是否为回文结构
         */
        public boolean isPail (ListNode head) {
        
            ArrayList<Integer> list = new ArrayList<>();
            while (head != null) {
        
                list.add(head.val);
                head = head.next;
            }
            int i = 0, j = list.size() - 1;
            while (i < j) {
        
                if (!list.get(i).equals(list.get(j))) {
        
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }
    
        /**
         * BM15 删除有序链表中重复的元素-I
         */
        public ListNode deleteDuplicates (ListNode head) {
        
            ListNode cur = head;
            while (cur != null && cur.next != null) {
        
                if (cur.val == cur.next.val) {
        
                    cur.next = cur.next.next;
                } else {
        
                    cur = cur.next;
                }
            }
            return head;
        }
    
        /**
         * BM16 删除有序链表中重复的元素-II
         */
        public ListNode deleteDuplicates2 (ListNode head) {
        
            ListNode fake = new ListNode(1001);
            fake.next = head;
    
            ListNode cur = fake;
            while(cur != null && cur.next != null && cur.next.next != null) {
        
                //发现有重复节点
                if (cur.next.val == cur.next.next.val) {
        
                    int val = cur.next.val;
                    //找到最后一个重复节点
                    ListNode tmp = cur.next.next;
                    while (tmp.next != null && val == tmp.next.val) {
        
                        tmp = tmp.next;
                    }
                    //重新连接
                    cur.next = tmp.next;
                    //当前节点不变
                } else {
        
                    cur = cur.next;
                }
            }
            return fake.next;
        }
    }