链表解决约瑟夫环问题

在一间房间总共有n个人（下标0～n-1）(也可以是 1 ~ n)，只能有最后一个人活命。

按照如下规则去排除人：

所有人围成一圈 顺时针报数，每次报到q的人将被排除掉 被排除掉的人将从房间内被移走 然后从被kill掉的下一个人重新报数，继续报q，再清除，直到剩余一人 你要做的是：当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来。

public class LeetCode {

    /**
     * 约瑟夫问题(约瑟夫环)
     *
     * @param args args
     */
    public static void main(String[] args) {
        // 初始化链表, 从1到41
        Node head = new Node(1);
        Node current = head;
        for (int i = 2; i <= 41; i++) {
            Node node = new Node(i);
            current.next = node;
            current = node;
        }
        // 连接首尾
        current.next = head;
        System.out.println(process(head, 3).val);
    }

    public static Node process(Node head, int m) {
        // m为每次跳过的人数, 先判断边界
        if (m == 1) return head;
        Node current = head;
        while (current.next != current) {
            // 注意这边当m=3的时候为什么循环两次, 因为current节点本身是1, 到3就KO
            // 未循环的时候 current是1, 循环一次current是2, 循环二次current就是第3位
            for (int i = 1; i < m; i++) {
                // 这边head当做临时缓存节点用
                head = current;
                current = current.next;
            }
            // 本来是 head -> current -> current.next
            // 现在直接连接 head -> current.next 代表把current踢出去
            head.next = current.next;
            // 当前节点指向他的下一节点, 再次循环(这一步就相当于报数1)
            current = current.next;
        }
        return current;
    }
}

class Node {
    Integer val;
    Node next;

    public Node(Integer val) {
        this.val = val;
    }
}

两个有序链表的合并

LeetCode 21 题: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解法一(迭代)

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 首先判断两个链表如果有null的情况
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        // 借助head节点
        ListNode r = new ListNode(-1);
        ListNode cur = r;
        // 如果l1 l2 都没有空的时候, 则比较大小并依次放入新链表
        // (因为都是递增的所以可以依次比较)
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 最后把还有剩余的链表挂到后面
        cur.next = l1 != null ? l1 : l2;
        return r.next;
    }

解法二(递归)

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 边界判断, 如果其中一个链表为null, 则直接把另一个链表挂到最后面
        if (l1 == null) return l2;
        else if (l2 == null) return l1;
        // 如果l1的值比l2小
        else if (l1.val < l2.val) {
            // 递归判断并给l1的next赋值, 递归的时候把l1当前节点去掉
            l1.next = mergeTwoLists(l1.next, l2);
            // 因为l1的值小, 所以先返回l1(升序)
            return l1;
        } else {
            // 否则就是l2小, l2执行上面的操作
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

删除链表的倒数第N个节点

LeetCode 19 题: 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 借助一个哑节点, 可以使慢指针刚好指到需要删除节点的前一个节点
        // 而且也不用考虑删除的节点就是头节点的情况
        ListNode dummy = new ListNode(-1, head);
        ListNode first = head;
        ListNode second = dummy;
        // 快指针先行n步
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        // 快慢指针一起循环, 直到快指针指到链表结尾
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        // 删除慢指针当前节点的后一个节点, 因为有哑节点存在
        second.next = second.next.next;
        return dummy.next;
    }