LeetCode 算法实践:链表元素移除与反转操作
第一题 - 移除链表元素
方法一 - 原地删除
思路阐述:要实现链表中指定值元素的删除,需分情况处理。一是头节点的值恰好为目标值,此时直接删除头节点并更新头指针;二是中间或尾部节点的值为目标值,需借助前驱节点来完成删除操作。
解题步骤:
- 删除头部目标节点:通过循环判断头节点是否存在且值是否等于目标值。若满足条件,先临时保存头节点,将头节点更新为下一个节点,再释放临时保存的头节点。
- 删除中间和尾部目标节点:初始化临时指针temp
指向新的头节点,遍历链表时确保当前节点及其下一个节点非空。若下一个节点的值等于目标值,临时保存该节点,将当前节点的next
指针指向其下下个节点,然后释放临时保存的节点;若下一个节点的值不等于目标值,将temp
指针后移。
- 返回新头节点:遍历结束后,返回更新后的头节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
while (head != NULL && head->val == val)
{
struct ListNode* tmp = head;
head = head->next;
free(tmp);
}
struct ListNode* temp = head;
while (temp != NULL && temp->next != NULL)
{
if (temp->next->val == val)
{
struct ListNode* cur = temp->next;
temp->next = cur->next;
free(cur);
}
else
{
temp = temp->next;
}
}
return head;
}
复杂度分析
- 时间复杂度:O(n),需遍历链表的每个节点一次。
- 空间复杂度:O(1),仅使用常数级额外空间存储指针变量。
方法二 - 双指针
思路剖析:利用双指针prev
和cur
遍历链表,当遇到值为目标值的节点时,调整指针跳过该节点并释放内存。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while (cur != NULL)
{
if (cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
if (cur == head && cur->val == val)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
}
return head;
}
代码分析
- 初始化双指针:prev
初始化为NULL
,用于记录当前节点的前一个节点;cur
初始化为头节点head
,用于遍历链表。
- 遍历链表:通过while
循环遍历链表,直到所有节点处理完毕。
- 处理当前节点:若当前节点值不等于目标值,更新prev
并后移cur
;若当前节点值等于目标值,根据是否为头节点分别处理,调整指针并释放内存。
- 返回头指针:遍历结束后,返回更新后的头指针。
方法三 - 尾插
思路讲解:遍历原链表,将不等于目标值的节点依次尾插到新链表中,最后返回新链表的头指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
while (cur)
{
if (cur->val != val)
{
// 尾插
if (tail == NULL)
{
newhead = tail = cur;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if(tail)
{
tail->next=NULL;
}
return newhead;
}
代码分析
- 初始化变量:cur
用于遍历原链表,初始化为原链表头head
;newhead
为新链表头指针,初始化为NULL
;tail
为新链表尾指针,初始化为NULL
,用于高效尾插节点。
- 遍历原链表:通过while
循环遍历原链表,处理每个节点。
- 处理当前节点:若当前节点值不等于目标值,根据新链表是否为空进行尾插操作;若当前节点值等于目标值,释放该节点并继续遍历。
- 处理尾节点指针:遍历结束后,确保新链表尾节点的next
指针为NULL
。
- 返回新链表头指针:返回新链表的头指针。
第二题 - 反转链表
描述:给定单链表的头节点head
,将链表反转并返回反转后的链表。
方法一 - 迭代
思路解析:使用三个指针协同工作,逐步将每个节点的next
指针指向前驱节点,实现链表反转。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* n1 = NULL;
struct ListNode* n2 = head;
struct ListNode* tmp = head;
while(tmp!=NULL)
{
tmp = n2->next;
n2->next=n1;
n1=n2;
n2=tmp;
}
return n1;
}
代码分析
- 初始化指针:n1
初始化为NULL
,指向当前处理节点的前驱节点;n2
初始化为头节点head
,指向当前正在处理的节点;tmp
初始化为头节点head
,作为临时指针保存后续节点。
- 遍历链表:通过while
循环确保遍历完整链表。
- 反转操作:保存后继节点,调整当前节点的next
指针指向前驱节点,然后移动指针继续处理。
- 返回新头节点:循环结束后,n1
指向原链表最后一个节点,即反转后的新头节点,返回n1
。
方法二 - 采用头插创建新链表
思路剖析:遍历原链表,为每个节点创建副本,将副本节点依次插入新链表头部,形成原链表的逆序。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* newHead = NULL; //新链表的头指针
while (cur)
{
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
if (newNode == NULL)
{
perror("malloc failed");
// 释放已分配的节点
while (newHead)
{
struct ListNode* temp = newHead;
newHead = newHead->next;
free(temp);
}
return NULL;
}
newNode->val = cur->val;
newNode->next = newHead; //头插法:新节点指向当前头
newHead = newNode; //更新头指针
cur = cur->next;
}
return newHead; //返回新链表的头结点
}
代码分析
- 初始化变量:cur
指向原链表当前节点,初始化为head
;newHead
为新链表头指针,初始化为NULL
。
- 遍历原链表:通过while
循环遍历原链表,为每个节点创建副本。
- 头插操作:将副本节点插入新链表头部,更新新链表头指针。
- 错误处理:若内存分配失败,释放已创建的新链表节点并返回NULL
。
- 返回结果:遍历结束后,返回新链表的头指针。
总结
至此,对链表相关操作的探索暂告一段落,但编程之路才刚刚起步。编写代码是与计算机逻辑深度交互的过程,虽会在结构设计和算法实现中遇到挑战,但这些经历能加深对代码逻辑和数据组织的理解。愿你在编程之路上持续探索,书写属于自己的精彩篇章,期待下次与你在代码世界中再度相逢,见证你的成长与进步。
文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/12853.html