前言：📫 作者简介：小明java问道之路，专注于研究计算机底层，就职于金融公司后端高级工程师，擅长交易领域的高安全/可用/并发/性能的设计和架构📫
🏆 Java领域优质创作者、阿里云专家博主、华为云享专家🏆
🔥 如果此文还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦
本文导读
字节跳动企业题库，链表系列，因为有leetcode会员能看到企业出题频率，那我们从出题频率最高刷到最低，题目有206. 反转链表 、19. 删除链表的倒数第 N 个结点
206. 反转链表
【简单】【题目描述】给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：输入：head = [1,2] 输出：[2,1]
示例 3：输入：head = [] 输出：[]
这道题是一到老生常谈的题目，对于熟悉链表的同学来说是秒杀的，我们分递归和迭代两种方法解题
【迭代、递归】图解：
代码详解，逐行注释：
public ListNode reverseList(ListNode head) { /*迭代法*/ ListNode prev = null; // 1 对于上图解析，先设置两个结点 ListNode curr = head; // 2 while (curr != null) { ListNode next = curr.next; // 3 反转 curr.next = prev; // 4 prev = curr; // 5 向前移动 curr = next; // 6 } return prev; } public ListNode reverseList(ListNode head) { /*递归法*/ if (head == null || head.next == null) { // 递归停止条件 return head; } ListNode newHead = reverseList(head.next); // 递归 head.next.next = head; // 1 将后一位指向前一位 head.next = null; // 2 断开前一位的next指针 return newHead; }
19. 删除链表的倒数第 N 个结点
【中等】【题目描述】给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]
示例 2：输入：head = [1], n = 1输出：[]
示例 3：输入：head = [1,2], n = 1输出：[1]
这是所有大厂最爱考的链表题目之一，对于熟悉链表的同学来说是秒杀的，我们用暴力法、快慢指针(双指针)法解题
代码详解，逐行注释：
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); // 保留的头节点 int length = getLength(head); // 获取链表长度 ListNode cur = dummy; for (int i = 1; i < length - n + 1; ++i) { // 遍历到 L-n+1的位置 cur = cur.next; } cur.next = cur.next.next; // 删除节点 ListNode ans = dummy.next; // 返回保留的头节点 return ans; } public int getLength(ListNode head) { /*遍历一遍，计算链表长度*/ int length = 0; while (head != null) { ++length; head = head.next; } return length; } public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); // 保留的头节点 ListNode first = head; // 快指针 ListNode second = dummy; // 慢指针 for (int i = 0; i < n; ++i) // 快指针先走的n的位置 first = first.next; while (first != null) { // 同时向后移动 first = first.next; second = second.next; } second.next = second.next.next; // 删除节点 ListNode ans = dummy.next; // 返回保留的头节点 return ans; }
