[LeetCode] 1290. 二进制链表转整数 (Convert Binary Number in a Linked List to Integer)

本文已收录于 LeetCode刷题 系列,共计 28 篇,本篇是第 18 篇

本文已收录到:LeetCode刷题 专题

题目

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

 

示例 1:

输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)
示例 2:

输入:head = [0]
输出:0
示例 3:

输入:head = [1]
输出:1
示例 4:

输入:head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出:18880
示例 5:

输入:head = [0,0]
输出:0
提示:

链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

视频讲解

[bilibili cid=”” page=”1″]285176133[/bilibili]

 

简明思路

先反转,再用指针实现 1*2的某次方操作(通过 << 运算实现)。

 

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        //反转链表
        ListNode* pre = nullptr;
        ListNode* cur = nullptr;
        ListNode* temp = head;

        while (temp != nullptr)
        {
            pre = cur;
            cur = temp;
            temp = cur->next;
            cur->next = pre;
        }

        ListNode* p = cur;
        int sum = 0;
        int i = 0;
        while (p != nullptr)
        {
            sum += p->val << i;
            i++;
            p = p->next;
        }
        return sum;
    }
};

 

 

作者: 高志远

高志远,23岁,男生,毕业于上海杉达学院电子商务系。

发表评论

邮箱地址不会被公开。