LeetCode

链表

// 单链表节点的结构

public class ListNode {
    int val;
    ListNode next;
    // 构造函数
    ListNode(int x) {
        val = x;
    }
}

链表反转

递归反转链表的一部分

1. 递归反转整个链表

明确递归函数的定义： 输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

---

2. 反转链表前N个节点

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode successor = null; // 后继节点
// 反转以head为起点的n个节点， 返回新的头节点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录n+1个节点
        successor = head.next;
        return head;
    }
    // 以head.next为起点， 需要反转前n-1个节点
    ListNode last = reverseN(head.next, n-1);
    head.next.next = head;
    // 让反转后的head节点和后面的节点连起来
    head.next = successor;
    return last;
}

---

3. 反转链表的一部分

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m-1, n-1);
    return head;
}

---

25.k个一组反转链表

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个节点反转
cur.next = pre;
// 更新指针位置
pre = cur; // 最后的值为最后的节点
cur = nxt; // 最后的值为NULL
}
// 返回反转后的头节点
return pre;
}

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}

----------------

ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0 ; i < k ; i++) {
// 不足k个， 不需要反转， base case
if (b == null)
return head;
b = b.next;
}
// 反转前k个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}

```

如何判断回文链表