算法题重点在于思路,代码其实并不难,这里的每一题都提供多种思路,大家可以动手写一下,并找到更好的解题方法
这里先介绍前三道
题目:
1.单链表相关经典算法OJ题1:移除链表元素
题目链接:https://leetcode.cn/problems/remove-linked-list-elements/description/
删除链表的指定元素
思路一:
让pcur找到要删除的元素,但是这样没法让链表连接,我们要在新建一个变量,来进行相连,还要有一个变量将pcur->next存下来,来释放pcur
思路二:
找值不为val的值然后将,尾插到新链表中
我们对这个方法进行代码实现:
此时运行
这里发现6并没有删除掉,原因就是5的节点仍然指向下一个节点
但这时又有问题了,我们对NULL指针进行解引用了,加一个判断如果newTail为NULL就部置NULL了
此时提交就通过了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
// 创建新链表的头和尾
ListNode* newHead = NULL;
ListNode* newTail = NULL;
ListNode* pcur = head;
while (pcur)
{
if (pcur->val != val)
{
if (newHead == NULL) // 链表为NULL
{
newHead = newTail = pcur;
} else
{
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
if(newTail)
newTail->next = NULL;
return newHead;
}
2.单链表相关经典算法OJ题2:反转链表
题目链接:https://leetcode.cn/problems/reverse-linked-list/description/
思路一:
创建新链表,将原来的数据进行头插入
思路二:
创建3个指针完成原链表的反转
创建三个指针n3指向n1,然后三个指针都向后走,再加上部分NULL的判定即可
1.n3走到NULL时就不能向下走了
2.链表为NULL就不能运行直接返回
这里提交即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
//判空
if(head == NULL)
{
return head;
}
ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)//如果n3不为NULL就继续向下
n3 = n3->next;
}
return n1;
}
3. 单链表相关经典算法OJ题4:链表的中间结点
相关链接:https://leetcode.cn/problems/middle-of-the-linked-list/
找到中间点,如果有两个中间点就是后一个
思路一:
遍历,count计算节点数,返回(count/2)的next节点
思路二:
快慢指针
创建两个指针让快指针刚好时慢指针的2倍,此时出现一下情况
思路理解了代码就好写了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
多画图,多分析,多尝试写代码相信你会有所收获的,加油!!!
标签:head,单链,ListNode,struct,NULL,next,链表,C语言,数据结构 From: https://blog.csdn.net/2302_82004664/article/details/137623132