《五月集训》（第十二天）- 链表

• 前言
• 一、题目
• 二、打卡（代码已 AC）

        今天算法的内容是：链表。
 

        题目一：LeetCode 1290. 二进制链表转整数 原题链接

        题目二：LeetCode 237. 删除链表中的节点 原题链接

        题目三：LeetCode 剑指 Offer II 024. 反转链表 原题链接

• 1、这是第一题的思路 + 代码

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        auto p = head, q = head;
        int cnt1 = 0;       

        while (p) {          // (1) cnt1 统计整个链表的长度
            p = p->next;
            cnt1 ++;
        }

        int sum = 0;
        int cnt2 = 0;       // cnt2 当前遍历到第几个节点
        while (q) {
            cnt2 ++;
            sum += q->val * pow(2, cnt1 - cnt2);
            q = q->next;
        }

        return sum;
    }
};

• 2、这是第二题的思路 + 代码

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

• 3、这是第三题的思路 + 代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        ListNode* a = NULL;
        ListNode* b = head;

        while (b) {
            auto c = b->next;
            b->next = a;
            a = b;
            b = c; 
        }
        return a;
    }
};