链表力扣例题
876. 链表的中间结点
给你单链表的头结点 head
,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
AC
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
代码思想
快慢指针,fast指针和slow指针都指向head,fast指针每次走两步,slow指针每次走一步,当将整个链表都遍历了一遍以后,fast指向了尾部(总节点数为奇数时指向尾部节点,总节点数为偶数时指向尾部节点的后面也就是空指针),而此时slow指针刚好指向的是中间节点(总节点数为偶数时则为第二个中间节点),此时返回slow指针即可。
203. 移除链表元素
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。
AC
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while(cur != NULL)
{
if(cur->val == val)
{
struct ListNode* next = cur->next;
if(prev)
prev->next = next;
else{
head = next;
}
free(cur);
cur = next;
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
代码思路
cur指针用来遍历链表,prev指针是cur指针指向节点的前一个节点,如果当前cur指向的节点需要进行删除的话,创建next变量保存cur的下一个节点地址,让prev指向next(这里需要考虑prev是否是空。是空的话,说明正在移除的元素是头指针,因为这是进入当前循环的条件,删除头指针的话,也就表示删除了链表的地址,会发生内存泄漏,因此需要将head调整到指向下一个元素,再进行释放;如果不是空,说明执行了cur->val == val这一个判断的else,已经不会改变头指针了,也就不会影响到链表地址),接着释放掉需要删除的节点(不释放会发生内存泄漏),然后cur此时是野指针,让他指向之前创建的next,也就是下一个节点;如果cur当前指向的值不需要删除,prev指向cur指向的地址,cur指向下一个节点。
链表本机调试tips
在本机调试链表是需要数据,按照链表的定义来进行创建的话,正常还需要写尾插函数等,比较繁琐,本机调试其实可以直接malloc出来,将数据直接写成链表,如下:
struct ListNode* n1(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n2(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n3(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n4(struct ListNode*)malloc(sizeof(struct ListNode));
n1->va1 = 1;
n2->va1 = 2;
n3->va1 = 3;
n4->Va1 = 4;
n1->next n2;
n2->next n3;
n3->next n4;
n4->next NULL;
这样就是一个1->2->3->4->NULL的链表了