1.反转链表（206-易）
题目描述：反转单链表 （迭代和递归实现）
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路：
法1：递归（自下向上）实现
- 递归函数是得到反转的链表
- 终止条件，只有一个节点或者节点为空
- 最后进行反转（递归的基本逻辑），不要忘记断开正向连接的指针。
法2：迭代遍历数组，修改指针，分三步：
- 记录head.next的值（防止指针丢失）
- 断指针，重新连接（反转）
- 移动pre和head指针
代码：
// 递归 public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); // 反转两个节点 head.next.next = head; head.next = null; return newHead; } // 迭代 public ListNode reverseList(ListNode head) { if (head == null) { return head; } ListNode pre = null, next; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }
2.反转链表II（92-中）
题目描述：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。即反转指定区间的链表。
示例:
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
思路：本题使用头插法+双指针反转链表，即定义双指针，一个指向区间起点的前一个节点pre，另一个指针cur遍历区间的链表进行头插。具体步骤如下：
- 定义虚拟节点dummy，便于返回结果
- 寻找pre节点（区间起点的上一个节点）
- cur指针遍历剩余区间的节点，从区间第二个节点开始（注意记录），依次取出，进行头插并连接。
注意两个细节：
- 头插法连接链表时，为了避免指针丢失，我们先连后边再连前边。
- 在寻找pre节点的时候，right边界也要跟着同步缩小
代码：
public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode pre = dummy; ListNode cur = dummy.next; while (left-- > 1) { pre = pre.next; cur = cur.next; right--; } while (right-- > 1) { ListNode remove = cur.next; cur.next = cur.next.next; remove.next = pre.next; pre.next = remove; } return dummy.next; }
3.交换链表中的相邻节点（24-中）
题目描述：两两交换相邻的节点，不修改val值，空间复杂度O(1)
示例：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
思路：本题可参考T206反转链表。
法1：使用递归求解，采用自上而下的递归（假设子链表已经满足条件）
- 递归函数：获取两两交换的子链表的头结点（注：函数输入为下一组的头节点）
- 终止条件：
head == null || head.next == null（没有节点或还有一个节点） - 递归逻辑：反转两个相邻的节点
法2：使用迭代（双指针），遍历链表，进行两两交换。几个注意点：
- 设置哨兵节点，便于结果返回
- pre指针维护每组交换的前驱节点
- 断（防止指针丢失，连接下一组节点）-> 反（反转本组两个节点）-> 连（连接上一组节点）。
链表问题一定要画图！
代码：
// 代码1：递归 public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; return next; } // 代码2：双指针 public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; ListNode l1, l2; while (pre.next != null && pre.next.next != null) { l1 = pre.next; l2 = pre.next.next; // 连接链表 l1.next = l2.next; l2.next = l1; pre.next = l2; // 更新一组交换节点的前驱节点 pre = l1; } return dummy.next; }
4.重排链表（143-中）
题目描述：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…，即重排链表保证头尾交替出现。
示例：
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
思路：由于链表不支持下标访问，并且单链表不能逆序查找节点。我们能想到比较容易想到的方案就是前两种：
法1：用List集合存储链表节点，这样就可以按照要求通过下标构建链表，使用了额外空间。
法2：将链表后半部分逆序，然后根据规则依次连接左右连部分。具体步骤是：
- 快慢指针找到链表中点，断开链表。注意偶数链表为下中间节点。
- 反转右半部分链表
- 定义指针，遍历两个链表并合并，注意保存下一个节点（防止指针丢失）
代码：
// 法1：线性表 public void reorderList(ListNode head) { if (head == null) { return; } List<ListNode> list = new ArrayList<>(); ListNode cur = head; while (cur != null) { list.add(cur); cur = cur.next; } int i = 0, j = list.size() - 1; while (i < j) { list.get(i).next = list.get(j); i++; list.get(j).next = list.get(i); j--; } list.get(i).next = null; } // 法2：反转右半部分链表 + 合并重排 public void reorderList(ListNode head) { // 1.找中点（偶数为右中点） if (head == null) return; ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 2.反转链表 ListNode right = slow.next; slow.next = null; ListNode rightHead = reverseList(right); // 3.合并重排链表 ListNode l1 = head, l2 = rightHead, next1, next2; while (l2 != null) { next1 = l1.next; next2 = l2.next; l1.next = l2; l1 = next1; l2.next = next1; l2 = next2; } } private ListNode reverseList(ListNode head) { ListNode pre = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }
5.旋转链表（61-中）
问题描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
案例：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
思路：
法1：闭合成环，先成环，然后断连接。注意更新有效的k值（即i）。
法2：类比T19题双指针，记数组长度为len，为了防止多次翻转，这里使用i = k % len，分为下边两种情况：
- i < len，直接类比T19题思路
- i == len，直接返回原链表
代码:
// 闭合成环 public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; int len = 1; ListNode cur = head; while (cur.next != null) { cur = cur.next; len++; } int i = len - k % len; if (i == len) return head; // 相当于每移动 cur.next = head; // 成环 while (i-- > 0) { cur = cur.next; } ListNode newHead = cur.next; cur.next = null; return newHead; } // 双指针 public ListNode rotateRight(ListNode head, int k) { if (head == null) return head; ListNode slow = head, fast = head; int i = k % length(head); if (i == 0) return head; while (i-- > 0) { fast = fast.next; } while (fast.next != null) { slow = slow.next; fast = fast.next; } ListNode newHead = slow.next; slow.next = null; fast.next = head; return newHead; } private int length(ListNode node) { if (node == null) return 0; return length(node.next) + 1; }
6.K 个一组翻转链表（25-难）
题目描述：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例:
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
思路：本题是对链表进行分区反转连接，即可以大致分为已反转、待反转和未反转。需要注意以下几点：
- 反转前，需要确定链表反转的范围k，即找到本次反转的尾结点；
- 需要记录每次待反转链表的前驱和末尾的后继节点，方便连接；
- 连接三部分之后，更新链表前驱和末尾节点的后继节点指针，进入下一次循环；
- 特殊的，当反转长度不足k时，即待反转链表末尾的后继节点为null，直接返回即可。
时间复杂度：O(KN)，空间复杂度O(1)。
代码：
public ListNode reverseKGroup(ListNode head, int k) { ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode pre = dummyHead; ListNode end = dummyHead; while (end.next != null) { for (int i = 0; i < k && end != null; ++i) { end = end.next; } if (end == null) break; ListNode start = pre.next; ListNode next = end.next; end.next = null; pre.next = reverse(start); start.next = next; pre = start; end = pre; } return dummyHead.next; } private ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head, next; while (cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }
7.奇偶链表（328-中）
题目描述：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例：
输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
思路：注意记录偶数位节点头部进行连接。
代码：
public ListNode oddEvenList(ListNode head) { if (head == null) { return head; } ListNode odd = head, even = head.next, evenHead = even; while (even != null && even.next != null) { odd.next = odd.next.next; odd = odd.next; even.next = even.next.next; even = even.next; } odd.next = evenHead; return head; }
