leetcode —— 简单链表题 C语言

一 、1290. 二进制链表转整数

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

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

int getDecimalValue(struct ListNode* head){
    struct ListNode *t=head;
    int a[100];
    int i=0;
    while(t!=NULL){
       i=i*2+t->val;
       t=t->next;
    }
    return i;
}

思路 ：每次进到下个链表就将前面的*2，并加上当前val.

二、237. 删除链表中的节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

void deleteNode(struct ListNode* node) {
    struct ListNode*t;
    node->val=node->next->val;
    node->next=node->next->next;
}

思路：只需将当前的改成下一个的就行.

三 、剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

struct ListNode* reverseList(struct ListNode* head){
    int a[10000];
    struct ListNode*t=head;
    int i=0;
    while(t){
        a[i++]=t->val;
        t=t->next;
    }
    t=head;
    for(int j=i-1;j>=0;j--){
        t->val=a[j];
        t=t->next;
    }
    return head;
}

思路：直接用一个数组记录数值 在反向给链表 

四 、1019. 链表中的下一个更大节点

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextLargerNodes(struct ListNode* head, int* returnSize){
    struct ListNode *t=head;
    int i=0;
    int len=0;
    while(t){
        t=t->next;
        len++;
    }
    int* a = (int*)calloc(sizeof(int), len);
    t=head;
    while(t){
        a[i++]=t->val;
        t=t->next;
    }
    *returnSize=len;
    t=head;
    int b;
    for(int k=0;ka[k]){
                b=1;
                a[k]=a[j];
                break;
            }
        }
        if(b==0) a[k]=0;
    }
    return a;
}

思路：直接赋值给数组 再双指针进行找最大值 用b标记 没有找到就改为0。

五、328. 奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

struct ListNode* oddEvenList(struct ListNode* head){
    if(head==NULL){
        return head;
    }
        struct ListNode *p3=head->next;
        struct ListNode *p=head;
        struct ListNode *p2=p3;
        while(p2!=NULL && p2->next!=NULL){
            p->next=p2->next;
            p=p->next;
            p2->next=p->next;
            p2=p2->next;
        }
       p->next=p3;
        return head;
}

思路 ：设三个链表分别为struct ListNode *p3=head->next;struct ListNode *p=head;
        struct ListNode *p2=p3;  在循环中首先将p->next指到p2->next->next 也就是第三个，

同理 将p=p->next,再将p2->next=p->next 最后再将p2改为p2->next.循环结束再将p和p2链接.

返回head.

六、725. 分隔链表

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

 

输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

struct ListNode** splitListToParts(struct ListNode* root, int k, int* returnSize) {
    *returnSize = k;
    struct ListNode** res = (struct ListNode**)calloc(k, sizeof(struct ListNode*));
    int n = 0;
    struct ListNode* cur = root;
    while (cur)
    {
        n++;
        cur = cur->next;
    }
    
    int split = n / k, last = n % k;
    int i = 0;
    if (split == 0)
    {
        while (last--)
        {
            res[i++] = root;
            cur = root->next;
            root->next = NULL;
            root = cur;
        }
    }
    else
    {
        while (k--)
        {
            res[i++] = root;
            for (int j = 0; j < split + (last > 0 ? 0 : -1); j++)
                root = root->next;
            last--;
            cur = root->next;
            root->next = NULL;
            root = cur;
        }
    }
    return res;
}

思路 ：首先算出链表长度 再用长度进行(除k)算出每组个数 再%k 算出剩多少个 再判断如果每组==0 那么直接进行分组 没有元素的为NULL，当>0 循环k次 每次将split个 （根据题意 前面的更大 所以需要判断last不为0 那么可以将加一进去）。输入链表数组中时 每次需要将其地址切断 设为NULL。  

来自英雄哪里出来的指导

题源 ：leetcode.