力扣链表刷题总结之c实现（常更）

落日映苍穹つ 2022-11-17 13:57 180阅读 0赞

1.力扣上的链表的头节点为真正意义上的头结点，也就是存值的第一个结点。在学习数据结构的时候我们都知道一般会设置一个头结点不存值，用来指向第一个存值的结点，真正存值的是头结点的后一个结点。而力扣山的头节点指的是存值的第一个结点，如果习惯了设置一个不存值的头结点，那么在对写的函数测试的时候将传入的头结点，改为head->next就ok了。

2.关于单链表的定义以及函数的定义，力扣已经默认设置好了，必须使用默认定义的单链表，并且不能修改函数名字，这个函数是后台测试的，修改了名字无法运行，但是可以自己再创建新的函数，套娃，另外就是可以通过typedef重新为定义的链表起个别名。  
关于力扣默认解题模板，个人觉得挺好，不过一些打比赛的小伙伴不是很喜欢这种形式，喜欢所有东西自己定义，然后自己写的是完整的程序，如果力扣可以自选方式就好了。  
![在这里插入图片描述][20210410101733328.png]  
3.当头节点或尾结点有可能发生变化需要单独考虑时，使用虚拟头节点可以避免复杂的分类讨论

struct ListNode *dummyNode = malloc(sizeof(struct ListNode));
    dummyNode->val = -1;
    dummyNode->next = head;

例如对于链表的索引为\[M, N\]的区间反转，此时头节点很可能在这个区间里面，加个虚拟结点，避免讨论头节点在这个区间里面和在这个区间外面的情况。

4.双指针解题思想，**注意当题目中出现距离k**时，这时候注意看看是否可以利用双指针，两个指针间距k，尤其是求链表的倒数第k个结点的问题就可以考虑双指针。

5.关于链表简单进行本地测试的代码：

#include<stdio.h>
    #include<stdlib.h>
    typedef struct ListNode{ 
         struct ListNode* next;
         int val;
    }ListNode;
    void CreateList(ListNode* head, int n)
    { 
         ListNode* p;
         ListNode* rear = head;
         for(int i=1; i<=n; i++)
         { 
              p = (ListNode* )malloc(sizeof(ListNode));
              p->val = i;
              rear->next = p;
              rear = p;
         }
         rear->next = NULL;
    }
    void PrintList(ListNode* head)
    { 
         ListNode* p = head;
         while(p)
         { 
              printf("%d ", p->val);
              p = p->next;
         }
    }
    
    int main()
    { 
         ListNode* head;
         head = (ListNode* )malloc(sizeof(ListNode));
         head->next = NULL;
    
         CreateList(head, 4);
         PrintList(head->next);
         
         //由于创建的是含头节点的链表，所以传入函数时传入head->next即可。
         //测试你的函数，传入头指针function(head->next);
    }

[20210410101733328.png]: /images/20221022/02b9db02080543b68cff2ddd125078e1.png