Leetcode 链表套餐小结
in LeetCode with 0 comment

Leetcode 链表套餐小结

in LeetCode with 0 comment
链表套餐: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;
}

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

链表合并

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

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

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号