NowCoderTOP1-6——持续更新ing

TOP1 反转链表

package NowCoder;

/**
 * 反转链表
 * 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 **/
public class top1 {
    public ListNode ReverseList(ListNode head) {
        // 新链表头节点指向空
        ListNode newHead = null;
        while (head.next != null) {
            // 1. 先保存下一个节点
            ListNode next = head.next;
            // 2. 原链表的第一个节点指向 newHead
            head.next = newHead;
            // 3. newHead指向head,head指向下一个节点
            newHead = head;
            head = next;
        }
        return newHead;
    }
}

TOP2 链表内指定区间进行反转

package NowCoder;

/** * 将链表指定位置进行反转 * 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 * 例如： * 给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL 1 → 2 → 3 → 4 → 5 → NULL, m=2,n=4m=2,n=4, * 返回 1\to 4\to 3\to 2\to 5\to NULL 1 → 4 → 3 → 2 → 5 → NULL. **/
public class top2 {
    
    /** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */
    public ListNode reverseBetween (ListNode head, int m, int n) {
    
        // 定义一个虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        // 前序节点
        ListNode pre = dummyHead;
        // 当前头节点
        ListNode cur = head;
        // 找到 m 所在的节点位置
        for (int i = 1; i < m; i++) {
    
            pre = cur;
            cur = cur.next;
        }
        // 此时已经找到了 m 节点所在的位置，遍历节点 m ~ n,反转链表
        for(int i = m; i < n ; i++) {
    
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummyHead.next;
    }
}

TOP3 链表中的节点每k个一组翻转

package NowCoder;

/** * 链表中的节点每k个一组翻转 * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 * 你不能更改节点中的值，只能更改节点本身。 **/
public class top3 {
    
    /** * @param head ListNode类 * @param k int整型 * @return ListNode类 */
    public ListNode reverseKGroup (ListNode head, int k) {
    
        // 运用递归的思想
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
    
            // 当尾节点遍历至空，直接返回其头节点
            if (tail == null) return head;
            tail = tail.next;
        }
        // 此时已经找到要翻转的区间
        // 定义前驱节点和当前节点
        ListNode pre = null;
        ListNode cur = head;
        // 此时tail指向下一个区间的首节点
        while (cur != tail) {
    
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        // 到这里一段区间的翻转已完成，递归拼接其他的区间
        // 递归下一区间，当前区间尾部指向下一个要翻转的链表
        head.next = reverseKGroup(tail, k);
        // 最后的 pre 指头节点
        return pre;
    }
}

TOP4 合并两个排序的链表

package NowCoder;

/** * 合并两个排序的链表 * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 **/
public class top4 {
    
    public ListNode Merge(ListNode list1,ListNode list2) {
    
        // 先判断 list1 和 list2 为空时
        if (list1 == null || list2 == null) {
    
            return list1 != null ? list1 : list2;
        }
        // 此时两个链表都不为空，递归比较两个链表中各元素的值
        if (list1.val <= list2.val) {
    
            list1.next = Merge(list1.next, list2);
            return list1;
        }else {
    
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}

TOP5 合并k个已排序的链表

package NowCoder;

import java.util.ArrayList;

/** * 合并k个已排序的链表 * 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 * 递归 * 终止条件： 划分的时候直到左右区间相等或左边大于右边。 * 返回值： 每级返回已经合并好的子问题链表。 * 本级任务： 对半划分，将划分后的子问题合并成新的链表。 **/
public class top5 {
     
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
    
        return divideMerge(lists, 0 , lists.size() - 1);
    }

    // 划分合并区间函数
    public ListNode divideMerge(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(divideMerge(lists,left,mid),divideMerge(lists,mid + 1,right));
    }

    // 合并两个链表
    public  ListNode Merge(ListNode list1 , ListNode list2) {
    
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        // 此时两个链表都不为空
        // 定义一个虚拟头节点
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        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 = list2;
        else cur.next = list1;
        // 返回虚拟头节点的下一个节点
        return  dummyHead.next;
    }
}

TOP6 判断链表中是否有环

package NowCoder;

/** * 判断链表中是否有环 * step 1：设置快慢两个指针，初始都指向链表头。 * step 2：遍历链表，快指针每次走两步，慢指针每次走一步。 * step 3：如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL。 * step 4：如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。 **/
public class top6 {
    
    public boolean hasCycle(ListNode head) {
    
        // 边界条件
        if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
    
                return true;
            }
        }
        return false;
    }
}
        while (fast != null && fast.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
    
                return true;
            }
        }
        return false;
    }
}