24. 两两交换链表中的节点

本题是一道模拟过程的题目。搞清楚两两交换的步骤之后，写出对应的代码也就不是难题了。不过在学习题解的过程中发现，两两交换的步骤也有很多种实现方式。自己在做题目的时候使用的思路如下：

进行两两交换之前，设置三个指针，分别指向dummy，head和head.next。因为需要指向head和head.next，所以需要预先判断这两者是否为null。其余交换步骤如图所示。
但可以发现，如果按照这种交换方法，当链表节点个数为偶数时，完成最后一对节点的交换时，cur会指向最后一个节点，此时tmp = cur.next.next会出现空指针异常。因此，在进行指针移位操作前，进行一次判断。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode tmp = head.next;
        while (pre.next != null && pre.next.next != null) {		// 确保之后还存在至少一对可交换节点
            cur.next = tmp.next;
            tmp.next = cur;
            pre.next = tmp;

            if (cur.next == null) {
                break;
            } else {
                tmp = cur.next.next;
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

卡哥博客内的Java题解的思路图解如下：

与自己的思路不同，题解选择存储head.next.next。在进行两两交换操作时，第二步改变head.next的next。
附记：本题还存在递归解法，因为时间问题今天没能学习，作为后续要处理掉的遗留问题之一。

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

最直观的思路就是通过一次遍历统计出链表的长度，然后再根据链表长度遍历到倒数第n个节点的前一个节点（想要对一个节点进行操作，必须移动到该节点的前一个节点），然后删除目标节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        ListNode dummy = new ListNode(0, head);
        int size = 0;
        while (cur != null) {	// 遍历链表，获取链表长度
            size++;
            cur = cur.next;
        }
        System.out.println(size);
        ListNode pre = dummy;
        cur = head;
        for (int i = 0; i < size - n; i++) {	// 移动到目标节点的前一个节点
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;	// 删除节点
        return dummy.next;
    }
}

题目提示存在只需遍历一次链表的方法。在自己做题的过程中没能想出来，查看卡哥给出的思路之后直呼精妙.jpg。这个方法使用了双指针，预先将双指针拉开n个节点的长度，当靠后的节点移动至链表的最后一个节点时，靠前的节点便正好移动到了目标节点的前一个节点（再次强调，想要对一个节点进行操作，必须移动到该节点的前一个节点），进行删除操作即可。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = dummy;
        for (int i = 0; i < n; i++) {
            pre = pre.next;		// 确保cur最后停在目标节点的前一个节点 #1
        }
        while (pre.next != null) {	// 确保cur最后停在目标节点的前一个节点 #2
            pre = pre.next;
            cur = cur.next;
        }
        cur.next = cur.next.next;	// 删除操作
        return dummy.next;

    }
}

面试题 02.07. 链表相交

待补

142.环形链表II

待补