在java中使用单链表和递归方法将二进制转换为十进制

Question

在java中如何使用单链表和递归方法将二进制转换为十进制？ :-s

例如：

输入： 1->0->0->NULL

输出： 4

Answer 1

递归有点棘手，因为您需要根据列表长度缩放 "earlier" 值，最简单的方法似乎是通过附加参数传递结果 "so far"。

class Node {
  int value;
  Node next;

  int toDecimal(int resultSoFar) {
    int resultSoFar = 2 * resultSoFar + value;
    return next == null ? resultSoFar : toDecimal(resultSoFar);
  } 

  int toDecimal() {
    toDecimal(0);
  }
}

Answer 2

试试这个（列表末尾没有空值）：

public Integer binToDec(LinkedList<Integer> list){
        Double size = (double) list.size();
        if(size == 0D) return 0;
        Integer number = list.getFirst();
        list.removeFirst();
        if(number != 0) return binToDec(list) + number*new Double(Math.pow(2D, size - 1)).intValue();
        else return binToDec(list);
    }

请注意，它会清除列表。

Answer 3

我能想到两种办法解决：

1- 如果列表长度已知：

// To find length of list
public int length(Node head) {
      int count = 0;
      while(head != null) {
         count++;
         head = head.next;
      }
      return count;
   }

public static int convertWhenLengthIsKnown(Node head, int len) {
      int sum = 0;
      if(head.next != null) {
         sum = convertWhenLengthIsKnown(head.next, len-1);
      }
      return sum + head.data * (int)Math.pow(2,len);
   }


   // Call this function as below:

convertWhenLengthIsKnown(head, length(head)-1);

如果我们不想计算长度，那么我们可以有一个全局可访问的总和变量，

private static int sum = 0;

public static int convert(Node head,int i) {

  if(head.next != null) {
    i = convert(head.next, i);
  }
  sum += head.data * (int)Math.pow(2,i);
  return i+1;
 }

// Call this function as below:

convert(head,0);

下面是节点class:

class Node {
   int data;
   Node next;

   Node(int data) {
      this.data = data;
   }
}

希望对你有帮助。

Answer 4

由于您没有说明您的链接列表，我认为它类似于 pbajpai21.

中的 Node class

在不知道链的长度的情况下，您可以在每个级别将值向左移动一个位置。

列表中每个节点的 class

class Node {
    int digit;
    Node child;

    Node(int data) {
        this.digit = data;
    }

    public int getDigit() {
        return digit;
    }

    public void setChild(Node child) {
        this.child = child;
    }

    public Node getChild() {
        return child;
    }
}

演示class

public class Bits {
    public static void main(String[] args) {
        int[] ints = new int[] {1, 0, 1, 0, 1, 0};
        Node parent = new Node(ints[0]);
        Node root = parent;
        for (int i = 1; i < ints.length; i++) {
            Node child = new Node(ints[i]);
            parent.setChild(child);
            parent = child;
        }

        long value = computeValue(0, root);
        System.out.println();
        System.out.println("value = " + value);
    }

    private static long computeValue(long parentValue, Node node) {
        if (node == null) {
            return parentValue;
        }
        // only to print the current digit
        System.out.print(node.getDigit());
        long value = (parentValue << 1) + node.getDigit();
        return computeValue(value, node.getChild());
    }
}

产出

101010
value = 42

在java中使用单链表和递归方法将二进制转换为十进制

convert binary to decimal using single linked list and recursive method in java

java

recursion