LeetCode笔记-链表 LinkedList

type

Post

status

Published

date

Jun 21, 2023

slug

summary

思路

使用dummy head的时机：当需要生成新链表时，可以简化头节点处理。

逆序操作单链表 = 后序递归，正序 = 前序递归

经典例题

2/445. Add two numbers, II


input: {
	1->2->3,
	1->0->0
}
output: { 2->2->3 }

两个表示倒序多位数的链表，输出表示结果的链表

II的话先reverse操作再reverse结果

思路：

使用dummyHead和curr插入节点，每个循环记录carry位

23. Merge K Sorted Lists

用minheap, 注意初始化堆时判断空列表。

（如果list非空则将头节点加入minheap）

141. Linked List Cycle

检测链表有没有环，经典快慢指针题，相遇说明有环。

142. Linked List Cycle II

在快慢指针相遇点和头节点同时开一个慢指针，相遇点即为环入口。

206. Reverse Linked List

反转链表

方法一：iteration


ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        ListNode* temp = curr->next;  // 先记录curr->next
        curr->next = prev;            // 把curr->next指向prev
        prev = curr;                  // 更新下一轮curr, prev
        curr = temp;
    }

    return prev;
}

方法二：recursion


ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* remain = reverseList(head->next);
    
    // remain->...->(head->next)->null, head
    head->next->next = head;
    head->next = nullptr;
    return remain;
}