约瑟夫环 (opens new window)

public class Josephus {
// 􀨧􀔎􁭓􀭭􀚍􀷄
public static int f(int n, int k) {
    // 􀦇􀺎􀝝􀹍􀓞􀓻􀕈􀒅􀚞􁬬􀢧 1
    if (n == 1) {
       return 1;
    }
    return (f(n - 1, k) + k - 1) % n + 1;
}

public static void main(String[] args) {
    int n = 10;
    int k = 3;
    System.out.println("最后留下的那个人的编号是:" + f(n, k));
}

}

206. 反转链表 - 力扣（LeetCode） (opens new window)

class Solution {
    public ListNode reverseList(ListNode head) {
            if(head==null) return head;
            if(head.next==null) return head;
            ListNode h=reverseList(head.next);
            ListNode t=h;
            while(t.next!=null) t=t.next;
            t.next=head;
            head.next=null;
            return h;
    }
}

优化后

class Solution {
    public ListNode reverseList(ListNode head) {
            if(head==null) return head;
            if(head.next==null) return head;
            ListNode h = reverseList(head.next);//执行完这句后，head.next是最后一个节点了，head.next后面的节点应该是head,head是最后一个节点
            // head.next是第二个节点
            head.next.next = head;
            head.next = null;
            return h;
    }
}

25. K 个一组翻转链表 - 力扣（LeetCode） (opens new window)

充分利用reverseKGroup()的定义

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素 
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
             // 不⾜ k 个，不需要反转，base case 
            if (b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素 
        ListNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);
        return newHead;
    }
    /* 反转区间 [a, b) 的元素，注意是左闭右开 */ 
    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre, cur, next;
        pre = null;
        cur = a;
        next = a;
        while (cur != b) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

23. 合并 K 个升序链表 - 力扣（LeetCode） (opens new window)

class Solution {
    // 优先队列
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        ListNode dummy=new ListNode(-1);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b) -> (a.val-b.val));
        for (ListNode head: lists) {
            if(head != null) pq.add(head);
        }
        while (!pq.isEmpty()){
            ListNode node = pq.poll();
            p.next = node;
            if(node.next != null){
                pq.add(node.next);
            }
            p = p.next;
        }
        return dummy.next;
    }
    // 分治合并
    // public ListNode mergeKLists(ListNode[] lists) {
    //     return merge(lists,0,lists.length - 1);
    // }

    // 顺序合并
    // public ListNode mergeKLists(ListNode[] lists) {
    //     ListNode ans = null;
    //     for (int i = 0;i < lists.length; ++i) {
    //         ans = mergeTwoLists(ans, lists[i]);
    //     }
    //     return ans;
    // }

    public ListNode merge(ListNode[] lists, int l,int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dum = new ListNode(0), cur = dum;
        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;
        }
        cur.next = list1 != null ? list1 : list2;
        return dum.next;
    }
}