当前位置：首页 > news >正文

链表OJ习题（1）

news 2025/8/26 16:48:54

一. leetcode 203 移除链表元素

迭代法

https://leetcode.cn/problems/remove-linked-list-elements/description/

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* pcur=head;ListNode* newHead,*newTail;newHead=newTail=NULL;while(pcur){if(pcur->val!=val){if(newHead==NULL){newHead=newTail=pcur;}else{newTail->next=pcur;newTail=newTail->next;}}pcur=pcur->next;} if(newHead)newTail->next=NULL;return newHead;
}

思路

遍历原链表，筛选出不等于目标值的节点

将筛选出的节点依次连接，形成新链表

最后为新链表的尾节点next指针置空，避免链表循环

解题过程

定义newHead和newTail指针，分别指向新链表的头和尾

pcur找到val不为指定的val值时，有两种情况：

1）新链表为空时，要将newHead和newTail都指向当前节点

2）新链表非空时，newHead作为新链表的头结点，无需做任何处理，将当前节点尾插到新链表末尾，newTail指向链表新的尾节点

pcur跳出循环有两种情况

1）初始链表为空链表，这时可以直接返回newHead

2）初始链表不是空链表，pcur一直遍历到为空，要记得将newTail的next指针置为空，防止连接到后面的节点

复杂度

时间复杂度: O(n)

空间复杂度: O(1)

二. leetcode 206 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

法一：头插法

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {ListNode* pcur=head;ListNode* newHead,*headNext;newHead=headNext=NULL;while(pcur){ListNode* next=pcur->next;if(newHead==NULL){newHead=headNext=pcur;headNext->next=NULL;}else{//头插newHead=pcur;newHead->next=headNext;headNext=newHead;}pcur=next;}return newHead;
}

思路

用headNext记录新的头结点newHead的下一个节点

每次循环先保存下一个节点，然后将原链表的节点头插到新链表中

移动指针继续遍历，最终newHead成为新表头

法二：迭代法

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {ListNode* prev=NULL;ListNode* pcur=head;while(pcur){ListNode* next=pcur->next;pcur->next=prev;prev=pcur;pcur=next;}return prev;
}

思路

用prev记录前节点

每次循环先保存下一个节点，再将当前节点的next指针指向prev节点

移动指针继续遍历，最终prev成为新表头

解题过程

先创建两个指针，pcur和prev

pcur用来遍历原链表，prev用来保存pcur节点的前一个节点

在遍历时，再创建next指针用来存储pcur节点的下一个节点，将pcur的next指针指向改变后，pcur继续遍历，跳出循环后prev即为新链表的头节点

复杂度

时间复杂度: O(n)

空间复杂度: O(1)

三. leetcode 876 链表的中间节点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

法一：计数法

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//节点个数ListNode*pcur=head;int count=0;while(pcur){count++;pcur=pcur->next;}int mid=count/2;ListNode* midNode=head;while(mid--){midNode=midNode->next;}return midNode;
}

思路

第一次遍历链表记录节点总个数

第二次遍历到中间节点返回该节点

复杂度

时间复杂度: O(n)

空间复杂度: O(1)

法二：快慢指针法

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow=head;ListNode* fast=head;while(fast!=NULL && fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}

思路

慢指针每次走一步，快指针每次走两步

快指针为空或快指针的下一个指针为空时，slow指针指向的节点即为中间节点

注意：循环条件中 fast!=NULL 必须放在前面。

复杂度

时间复杂度: O(n)

空间复杂度: O(1)

四. leetcode 21 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode*l1,*l2,*l3;l1=list1;l2=list2;ListNode*newHead,*newTail;newHead=newTail=(ListNode*)malloc(sizeof(ListNode));//后面会用到newTail的next指针，所以需要初始化newTail->next=NULL;//l1用来遍历List1，l2用来遍历List2while(l1!=NULL && l2!=NULL){if(l1->val<l2->val){newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{newTail->next=l2;newTail=newTail->next;l2=l2->next;}}//遍历完l2跳出循环if(l1){//将newTail的next指针指向l1可直接将l1后面的节点连接起来newTail->next=l1;}//遍历完l1跳出循环if(l2){//将newTail的next指针指向l2可直接将l2后面的节点连接起来newTail->next=l2;}ListNode* retNode=newHead->next;//申请完空间要释放free(newHead);newHead=NULL;return retNode;
}

思路

创建虚拟头结点

创建两个指针分别遍历两个链表，每次取较小的节点接入新链表

拼接剩余未遍历完的链表

释放虚拟节点，返回新的链表头节点

复杂度

时间复杂度: O(n)

空间复杂度: O(1）

五. 牛客网链表分割

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode* lessHead,*lessTail;lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead,* greaterTail;greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));ListNode* pcur=pHead;while(pcur){if(pcur->val<x){lessTail->next=pcur;lessTail=lessTail->next;}else{greaterTail->next=pcur;greaterTail=greaterTail->next;}pcur=pcur->next;}greaterTail->next=NULL;lessTail->next=greaterHead->next;ListNode* ret=lessHead->next;free(lessHead);lessHead=NULL;return ret;}
};

思路