代码随想录刷题笔记（DAY4）

今日总结：今天把中心放在前端学习上，最后一个题没有完全理解，明天早起补上吧。勉强算完成任务。

Day 4

01. 两两交换链表中的节点（No. 24）

题目链接

代码随想录题解

1.1 题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

1.2 笔记

先来分析需不需要虚拟头节点，虚拟头节点是为了让处理头节点的方式和处理其他节点的方式相同，不用再单独写出来，所以先考虑头节点和其他节点的处理方式是否一样：

交换一个中间的节点需要哪些操作呢？

需要将前一个节点，也就是上图第一个点指向第三个点，但是头节点并没有前一个节点，所以我们得出头节点和其他节点的处理方式是不同的，所以引入虚拟头节点。（上图是要进行的操作，标号不代表顺序）

也很容易能看出，要交换两个节点需要前一个节点和后一个节点，所以我们的 cur 要定义在前一个节点：

这里我们先给上个图加上序号

1. 先让 cur 指向它的下下个节点（3 节点），但这时我们发现 cur 的下一个节点（2 节点）是不可达的，定义 temp1 指向这个节点

2. 使得 temp1 （节点 2 ）的下一个节点指向 （节点 4）

3. 让 （节点 3）再指向 （节点2）这样拉直后就实现了反转

接下来我们来看循环遍历的出口，如果是偶数个元素的话我们要保证 cur 后面有一个元素（有一个元素就代表后面还有一组元素，还需要循环交换），奇数个元素的话则需要保证 cur 的后面有两个个元素就结束（有两个元素才需要交换，一个的话不需要交换直接结束），先尝试写出循环遍历的出口

while(cur.next.next != null)
while(cur.next != null)

很明显看出这两个是包含关系，则可以写出

while(cur.next != null && cur.next.next != null)

1.3 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0, head); // 虚拟头节点
        ListNode cur = dummyHead;
        ListNode temp1; // 临时节点
        ListNode temp2;
        while (cur.next != null && cur.next.next != null) {
            temp1 = cur.next;
            cur.next = cur.next.next;
            temp1.next = cur.next.next;
            cur.next.next = temp1;
            cur = cur.next.next;
        }
        return dummyHead.next;
    }
}

02. 删除链表的倒数第 N 个结点（No. 19）

题目链接

代码随想录题解

1.1 题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

1.2 笔记

这道题的关键是如何找到删除节点的前一个节点，然后我们只需要让 node.next = node.next.next 就完成了删除操作，下面来思考如何找到这个节点呢？

因为题目里面给的是倒数第 N 个节点，所以很容易想到倒序遍历链表，回顾一下如何倒序遍历链表呢？

public void backtracking(ListNode head) {
	if (head.next == null) {
        // 到了最后一个节点
        return head;
    }
    ListNode node = head; // 记录当前栈中的 head
    backtracking(head.next);
    System.sout.println(node); // 实现倒叙输出
}

这道题的思路就变得清晰起来了，递归遍历到最后一个节点然后我们开始计数，直到倒数第 N 个节点的前一个节点，就比如 1 的话需要在倒数第二个栈执行操作，可以写出

        if (--N == 0) {
            // 要删除的节点的前一个节点
            node.next = node.next.next;
            return;
        }

下面给出完整的代码

1.3 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    int N = 0;
    ListNode dummyNode = new ListNode();
    public ListNode removeNthFromEnd(ListNode head, int n) {
        N = n;
        dummyNode.next = head;
        backtracking(dummyNode);
        return dummyNode.next;
    }
    public void backtracking(ListNode head) {
        if (head.next == null) {
            // 最后一个节点
            return;
        }
        backtracking(head.next);// 递归遍历节点
        ListNode node = head;
        if (--N == 0) {
            // 要删除的节点的前一个节点
            node.next = node.next.next;
            return;
        }
        return;
    }
}