您现在的位置是:首页 >技术杂谈 >【Leetcode -19.删除链表的倒数第N个结点 -24.两两交换链表中的节点】网站首页技术杂谈
【Leetcode -19.删除链表的倒数第N个结点 -24.两两交换链表中的节点】
简介【Leetcode -19.删除链表的倒数第N个结点 -24.两两交换链表中的节点】
Leetcode -19.删除链表的倒数第N个结点
题目:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1, 2, 3, 4, 5], n = 2
输出:[1, 2, 3, 5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1, 2], n = 1
输出:[1]
我们的思路是,创建一个哨兵位,使用快慢指针,快指针从head开始走,慢指针从哨兵位开始走,快指针先走n步,加上哨兵位,和慢指针拉开n+1步,这样才可以使要删除的结点的上一个结点直接指向要删除的结点的下一个结点,即删除倒数第n个节点;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
//创建一个哨兵位,它的next是head
struct ListNode* p = malloc(sizeof(struct ListNode));
p->val = 0;
p->next = head;
//fast从头结点开始,slow从哨兵位开始
//fast和slow拉开n个距离,加上哨兵位,实际上是n+1个距离
//这样才可以使要删除的结点的上一个结点直接指向要删除的结点的下一个结点
struct ListNode* fast = head, * slow = p;
for (int i = 0; i < n; i++)
{
if (fast == NULL)
{
return NULL;
}
fast = fast->next;
}
//然后fast和slow同时走,当fast为空,slow的next就是要删除的结点
while (fast)
{
slow = slow->next;
fast = fast->next;
}
//更新slow即可
slow->next = slow->next->next;
//需要返回哨兵位的next,因为如果要删除的结点是头结点,返回头结点就不行
struct ListNode* curr = p->next;
free(p);
return curr;
}
Leetcode - 24.两两交换链表中的节点
题目:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。
必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1, 2, 3, 4]
输出:[2, 1, 4, 3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
我们的思路是,在交换两个节点前设定一个节点curr,每次curr后面的两个节点交换;
初始定义:
第一次交换:
更新curr:
上图之后再次进入循环,node1和node2继续迭代:
后面的图省略,代码如下:
struct ListNode* swapPairs(struct ListNode* head)
{
//创建一个哨兵位
struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
dummyHead->val = 0;
dummyHead->next = head;
//curr从哨兵位开始
struct ListNode* curr = dummyHead;
//每次交换的是curr的后两个节点
while (curr->next && curr->next->next)
{
struct ListNode* node1 = curr->next;
struct ListNode* node2 = curr->next->next;
curr->next = node2;
node1->next = node2->next;
node2->next = node1;
//更新curr
curr = node1;
}
head = dummyHead->next;
free(dummyHead);
return head;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。