链表

链表定义

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; }
}

206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        ListNode next = null;
        while (curr != null) {
            next = curr.next; // 保存指向下一个节点的指针
            curr.next = prev; // 当前节点指向上一个节点，即反向
            prev = curr;      // 保存上一个节点
            curr = next;      // 操作下一个节点
        }
        return prev;
    }
}

https://leetcode.cn/problems/reverse-linked-list

203. 移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0); // 使用虚拟头节点，避免专门判断为头节点的情况
        dummy.next = head;
        ListNode curr = dummy;
        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

https://leetcode.cn/problems/remove-linked-list-elements

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

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 以 [1,2,3,4] 为例：
        ListNode dummy = new ListNode(0); // 虚拟头节点 -> [0,1,2,3,4]
        dummy.next = head;
        ListNode prev = dummy; // 当前节点的上一个节点
        ListNode curr = head;
        while (curr != null && curr.next != null) { // 以交换第一对 [1,2] 为例：
            prev.next = curr.next;          // 0 -> 2
            ListNode next = curr.next.next; // 保存下一对的第一个节点：3
            curr.next.next = curr;          // 2 -> 1
            curr.next = next;               // 1 -> 3
            prev = prev.next.next;
            curr = curr.next; // 遍历到下一对的第一个节点
        }
        return dummy.next;
    }
}

https://leetcode.cn/problems/swap-nodes-in-pairs

237. 删除链表中的节点

class Solution {
    public void deleteNode(ListNode node) {
        if (node != null && node.next != null) {
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }
}

https://leetcode.cn/problems/delete-node-in-a-linked-list

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        ListNode right = head; // 使用双指针实现滑动窗口
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        while (right != null) { // 移动滑动窗口至链表最末端
            curr = curr.next;
            right = right.next;
        }
        curr.next = curr.next.next; // 删除倒数第 n 个节点
        return dummy.next;
    }
}

https://leetcode.cn/problems/remove-nth-node-from-end-of-list