Leetcode 链表套餐小结

链表套餐:https://leetcode.com/tag/linked-list/ , 基本把链表套餐内 Medium 难度以上的题目刷了一遍，总结一下常见套路。

新建链表

基础操作

ListNode *ans = new ListNode(-1);
ListNode *last = ans, *temp = NULL;

ans->next作为答案返回

last用于记录下一个/上一个节点的位置，取决于正序还是倒序

temp 用于生成新的节点用，如果想不来原始节点修改方法，可以不动原始链表，直接新建节点，然后拼凑答案。

比如这样新建 temp = new ListNode(head->val);

各种转置

主要需要记住：

last 用于标注 上一个用过的节点
next 用于标注 下一个一会要用的节点

while (head) {
    //next 暂时记住当前节点的下一个节点
    next = head->next;
    //把新的节点放到第一个位置去（ans->next 是返回值）
    ans->next = head;
    // 上一个节点当做当前节点的下一个节点
    head->next = last;
    last = head;
    head = next;
}

c在全部转置的基础上(206. Reverse Linked List)，还有部分转置(92. Reverse Linked List II)，基本就那么回事。

链表合并

一般来说还会要求合并之后的链表有序，大致有两钟操作：

• 正常链表合并
• 如果实在写不来，把链表都赛到vector里边去，用vector处理好，用新建链表 的方法，把vector里边的东西搞成链接再返回。

目前能想到的就是这样，想不来的时候画一下链表结构会比较好。