原文链接: https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer

英文原文

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

 

Example 1:

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

Example 2:

Input: head = [0]
Output: 0

Example 3:

Input: head = [1]
Output: 1

Example 4:

Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880

Example 5:

Input: head = [0,0]
Output: 0

 

Constraints:

• The Linked List is not empty.
• Number of nodes will not exceed 30.
• Each node's value is either 0 or 1.

中文题目

给你一个单链表的引用结点 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。

通过代码

高赞题解

方法一：直接遍历，此种方法相当于反向操作，与十进制的链表转换成十进制数同理，用（res * 10 + head.val）就可以恢复成十进制数，不信 你拿笔模拟一下~

class Solution {
    public int getDecimalValue(ListNode head) {
        int res = 0;
        while(head != null){
            res = res * 2 + head.val;
            head = head.next;
        }
        return res;
    }
}

方法二，由于左移相当于乘以2，所以将方法一的乘以2替换成左移操作即可

class Solution {
    public int getDecimalValue(ListNode head) {
        int res = 0;
        while(head != null){
            res = (res << 1) + head.val;
            head = head.next;
        }
        return res;
    }
}

方法三：递归，参考leetcode题库中逆序打印链表的思路

class Solution {
    int count = 0;
    int res = 0;
    public int getDecimalValue(ListNode head) {
        if(head == null) return 0;
        res += getDecimalValue(head.next) + head.val * Math.pow(2, count);
        count++;
        return (int)res;
    }
}

方法四：栈

class Solution {
    public int getDecimalValue(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }
        int n = 0;
        int res = 0;
        while(!stack.empty()){
            res += stack.pop() * Math.pow(2, n);
            n++;
        }
        return (int)res;
    }
}

方法五：ArrayList

class Solution {
    public int getDecimalValue(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        int n = 0;
        int res = 0;
        for(int i = list.size()-1; i >= 0; i--){
            res += list.get(i) * Math.pow(2, n);
            n++;
        }
        return (int)res;
    }
}

方法六：比较原始的做法，先得出总长度，再从最低位恢复出十进制

class Solution {
    public int getDecimalValue(ListNode head) {
        int count = 0;
        int res = 0;
        ListNode p = head;
        while(p != null){
            count++;
            p = p.next;
        }
        while(head != null){
            res += head.val * Math.pow(2, count - 1);
            head = head.next;
            count--;
        }
        return (int)res;
    }
}

方法七：转化为字符串，再采用valueOf

class Solution {
    public int getDecimalValue(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while(head != null){
            sb.append(head.val);
            head = head.next;
        }
        return Integer.valueOf(sb.toString(), 2);
    }
}

统计信息

通过次数	提交次数	AC比率
55749	69003	80.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言