题目:给你一个单链表的引用结点 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
我们的思路是,定义一个sum = 0,每次sum向左移,右边补0,用sum的最低位0去按位或head的val,就能得到val的值,然后head往后走,sum也往左移,继续按位或链表的下一个值,直到head为空;
int getDecimalValue(struct ListNode* head)
{
//定义sum为0,由于链表中的值不是0就是1
//所以每次都用sum的最低位0去按位或上head的val,即可得到val
//每次按位或完,head往后走;sum向左移,右边会补0
int sum = 0;
while (head)
{
sum <<= 1;
sum |= head->val;
head = head->next;
}
return sum;
}
题目:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例: 输入:head = [1, 3, 2] 输出:[2, 3, 1]
限制: 0 <= 链表长度 <= 10000
我们的思路是,先将链表反转,并用count计算链表长度,然后开辟一个数组空间,将反转后的链表的val放到数组中,返回数组;
int* reversePrint(struct ListNode* head, int* returnSize)
{
//链表为空,长度返回0,返回空
if (head == NULL)
{
*returnSize = 0;
return NULL;
}
//count计算链表长度
//反转链表
int count = 0;
struct ListNode* curr = head, * prev = NULL;
while (curr)
{
struct ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
//开辟一个数组返回
//更新返回长度
int* p = (int*)malloc(sizeof(int) * count);
*returnSize = count;
//将反转后链表中的val放到数组中
for (int i = 0; i < count; i++)
{
p[i] = prev->val;
prev = prev->next;
}
return p;
}