hot100 -- 链表（中）-EW帮帮网

不要觉得力扣核心代码模式麻烦，它确实比不上ACM模式舒服，可以自己处理输入输出

只是你对链表和 return 的理解不到位

👂 ▶ 屿前世 (163.com)

👂 ▶ see you tomorrow (163.com)

🎂两数相加

🎂两数相加

2. 两数相加 - 力扣（LeetCode）

1）l1, l2 长度可能不一样，假设短的后面全是 0，通过三目运算符得到当前节点的值，比如
n1 = l1 ? l1->val : 0
2）sum = n1 + n2 + 进位，%10 当前位，/10 进位

3）注意给节点赋值方式
tail->next = new ListNode(...);
4）可能漏最后一次进位，while() 结束后还要来一次

时间 O(max(m, n))，空间 O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;

        int temp = 0; // 进位
        while (l1 || l2) {
            int n1 = l1 ? l1->val : 0; // l1 的值
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + temp;

            if (!head) // 第1次
                head = tail = new ListNode(sum % 10); // 注意赋值方式
            else {
                // tail 上一步已经初始化, 所以现在是 tail->next
                tail->next = new ListNode(sum % 10); // 先给下一赋值
                tail = tail->next; // 再移动
            }

            temp = sum / 10; // 进位
            
            // l1, l2 向后移动
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        // 最后一次进位
        if (temp) 
            tail->next = new ListNode(temp);

        return head; // 不返回 tail, 防止 nullptr
    }
};

🚩删除链表倒数第 N 个节点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

注意：链表的题，如果出现 Node->next，那么这个 Node 一定不为 nullptr，否则会报错

1，双指针：一前一后，前面的先移动 n 个位置，然后开始同步移动

2，栈：思路类似双指针，最终都是遍历到待删除节点前一个（从栈顶开始出栈）

3，链表长度：思路类似前面，借助哑节点，避免对删除头节点的处理，遍历两次即可

AC 双指针

时间 O(L)，空间 O(1)，L 链表长度

自己写的

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head, *slow = head;
        // 前后指针 -- 找到倒数第 n 个节点, 即 slow
        while (n--)
            fast = fast->next;

        // 删除头节点
        if (!fast) {
            ListNode *temp = head;
            head = temp->next;
            delete temp;
            return head;
        }

        while (fast->next)
            slow = slow->next, fast = fast->next;

        // 删除 slow 下一节点
        ListNode *bad = slow->next; // 要删除的节点
        slow->next = slow->next->next;

        bad->next = nullptr;
        delete bad;

        // 上面处理了头节点被删除的情况，所以这里可以 return head
        return head; 
    }
};

官解重写

删除倒数第 n 个节点，通过指针的 next 来操作，最后的 delete 只是为了手动释放堆区数据（自己new的自己delete）

bad 的作用是，防止删的是第一个元素，因为最终会遍历到删除节点的前一个

如果不用 bad，就像前面的代码一样，特殊处理删除节点是头节点的情况

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 初始化 head 上一位置,  bad->next = head
        ListNode *bad = new ListNode(0, head); 
        ListNode *fast = head, *slow = bad; // slow 初始化为 bad

        while (n--)
            fast = fast->next;

        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        // 此时 slow 位于删除节点 上一位置
        slow->next = slow->next->next; // 更新连接
        ListNode *ans = bad->next; // 新的头节点
        delete bad;
        
        return ans; // 返回新的头节点
    }
};

AC 栈

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        stack<ListNode *> s;
        // temp 的作用是，防止删的是第一个元素，因为最终会遍历到删除节点的前一个
        ListNode *temp = new ListNode(0, head);
        ListNode *cur = temp;
        // 链表节点全部入栈
        while (cur) {
            s.push(cur); // push_back 是 vector
            cur = cur->next;
        }
        // 弹出 n 个元素后，栈顶就是待删除节点前一个
        while (n--) 
            s.pop();
        
        ListNode *prev = s.top(); 
        prev->next = prev->next->next; // 先重新连接

        ListNode *ans = temp->next; // 再赋值新的头节点

        delete temp;

        return ans;
    }
};

AC 计算链表长度

同样，类似上面两种，通过头节点前的，哑节点，避免对删除头节点这种情况的处理

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *temp = new ListNode(0, head); // 哑节点，避免对头节点删除的处理
        ListNode *cur = temp;
        int len = 0;
        // 链表长度
        while (cur->next) { // 长度容易错
            len++;
            cur = cur->next;
        }
        cur = temp;
        int count = len - n;
        // 哑节点移动 len - n + 1，即待删除节点
        // 所以，移动 len - n，刚好待删除前一个
        while (count--) 
            cur = cur->next;
        cur->next = cur->next->next;
        ListNode *ans = temp->next; // 新的头节点
        delete temp;

        return ans;
    }
};

🌼两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

AC 递归

head之前的不用处理，举个例子，比如

转换后 head = swapPairs(temp->next)，把两两视作一个整体，那么两两中的后一个，指向哪里，取决于后面递归的结果，所以只需考虑当前层

时间 O(n)，空间 O(n)（递归栈深度 n）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // head 表示递归时，当前两两交换节点的前一个
    ListNode* swapPairs(ListNode* head) {
        // 递归出口
        if (head == nullptr || head->next == nullptr)
            return head; // 只剩0个 或 1个节点
            
        // 只看当前层：交换两个节点
        ListNode *temp = head->next; 
        head->next = swapPairs(temp->next); // 递归交换剩余节点
        temp->next = head;
        return temp; // 返回新的头节点
    }
};

AC 迭代

类似冒泡排序，直接交换，但是需要借助哑节点 temp，比如

temp->Node1->Node2

👇

temp->Node2->Node1

时间 O(n)，空间 O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *temp = new ListNode(0, head); // 初始 temp->next == head
        ListNode *tempHead = temp; // 头节点前一个
        // 递归中的 head 是当前节点
        // 迭代中的 head 只表示原链表头节点
        // 所以 while 中不能用 head, 应该用 temp
        while (temp->next != nullptr && temp->next->next != nullptr) {
            ListNode *Node1 = temp->next;
            ListNode *Node2 = temp->next->next;
            // temp->Node1->Node2 ----> temp->Node2->Node1
            temp->next = Node2;
            Node1->next = Node2->next;
            Node2->next = Node1;
            // 新的哑节点
            temp = Node1;
        }
        ListNode *ans = tempHead->next; // 新链表头节点
        // delete tempHead; // 删除哑节点
        return ans; // 新的头节点
    }
};

🌼K 个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

模拟：迭代反转 + 新建连接

以下是新建连接的 3 个步骤

k = 3 也一样

和上/下一组新建连接时，要从外层开始，就是p0->next->next到p0->next最后才是p0
p0->next->next = cur; // 下一组头
p0->next = nex; // 上一组尾
p0 = p1; // 更新p0

时间 O(n)，空间 O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 链表长度 len
        int len = 0;
        for (ListNode *cur = head; cur; cur = cur->next)
            len++;

        // temp->next  ==  head（temp/p0 -- 哑节点/哨兵节点）
        ListNode *temp = new ListNode(0, head);
        ListNode *p0 = temp; // p0 k个一组第一个节点的前一个

        ListNode *nex = nullptr, *cur = head;
        // k 个一组反转
        for (; len >= k; len -= k) {

            // 迭代 -- 反转（参考反转链表I）
            // 因为哨兵节点的存在，所以是 k 次而不是 k-1 次反转
            for (int i = 0; i < k; ++i) { // k 次反转
                ListNode *pre = cur->next; // pre 右移
                cur->next = nex; // 反转
                nex = cur; // nex 右移
                cur = pre; // cur 右移
            }

            // 当前组 与 上一组尾&&下一组头 连接
            ListNode *p1 = p0->next; // 新的p0
            p0->next->next = cur; // 下一组头
            p0->next = nex; // 上一组尾
            p0 = p1; // 更新p0
        }

        return temp->next; // 返回新链表的头节点
    }
};

hot100 -- 链表（中）

🎂两数相加

🚩删除链表倒数第 N 个节点

AC 双指针

AC 栈

AC 计算链表长度

🌼两两交换链表中的节点

AC 递归

AC 迭代

🌼K 个一组翻转链表

网站公告

今日签到

热门文章

最新发布