数据结构：单链表的应用（力扣算法题）第一章

每题代码汇总：登录 - Gitee.com

关于使用VS调试OJ代码，见：使用VS调试OJ代码-CSDN博客

基础单链表知识，见：数据结构：单链表（详解）-CSDN博客

1.移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

首先理解题意：

以及力扣已经提供了单链表的节点结构和待实现的函数。

思路一：

遍历链表，查找值为val的节点，并返回节点，删除指定位置的节点，再return，时间复杂度为O（n^2)

这样的代码直观但效率不高。

大致的逻辑：
while(遍历）
{//SLTNode* SLTFind(x);//SLTErase(pos);
}

代码：

typedef struct ListNode ListNode;//自定义，方便后续引用
//查找
ListNode* SLTFind(ListNode* phead, int val)
{ListNode* pcur = phead;while(pcur){if(pcur->val == val){return pcur;}pcur = pcur->next;}return NULL;
}
//删除
void SLTErase(ListNode** pphead,ListNode* pos)
{assert(pphead && pos);//pos为头节点if(pos == *pphead){*pphead = pos->next;free(pos);return;}else{ListNode* prev = *pphead;while(prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* pos;while((pos = SLTFind(head,val))!= NULL){SLTErase(&head,pos);}return head;
}

最终通过测试。

思路二：

创建新链表，将原链表中不为val的节点拿下来尾插。时间复杂度：O(N)。

newHead为新链表头指针，newTail为新链表尾指针，pcur为遍历原链表的指针。

基本逻辑：
while(遍历)
{//尾插
}

代码：

typedef struct ListNode ListNode;//自定义，方便后续引用
struct ListNode* removeElements(struct ListNode* head, int val) {//创建新链表ListNode* newHead,*newtail;newHead = newtail = NULL;ListNode* pcur = head;while(pcur){//判断if(pcur->val != val){//尾插if(newHead == NULL){//链表为空newHead = newtail = pcur;}else{//链表非空newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if(newtail)newtail->next = NULL;//避免残留原链表的指针return newHead;
}

最终通过测试。

2.反转链表

206. 反转链表 - 力扣（LeetCode）

理解题意：

思路一：

创建新链表，遍历原链表将节点头插到新链表中，时间复杂度：O(N)。

代码见下：

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

最终通过测试。

思路二：

创建n1,n2,n3三个指针，改变指针的指向。

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL){return head;}//创建三个指针ListNode*n1,*n2,*n3;n1 = NULL, n2 = head, n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;
}

最终通过测试。

3.链表的中间结点

876. 链表的中间结点 - 力扣（LeetCode）

理解题意：

思路一：

求得链表总长度，根据下标，总长度/2就是中间节点，再遍历找到中间节点及新链表。时间复杂度：O(N)。

代码如下：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {int len = 0;ListNode* curr = head;while(curr){len++;curr = curr->next;}int mid = len / 2;curr = head;for(int i = 0;i < mid; i++){curr = curr->next;}return curr;
}

最终测试通过。

思路二：

使用快慢指针法，慢指针每次走一步，快指针每次走两步。

代码：

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;
}

注意：在while循环中，不能将条件改为fast->next != NULL && fast != NULL，否则会导致空指针解引用错误（具体错误：当fast为NULL时，会先尝试访问fast->next,导致崩溃)，在涉及指针的条件表达式时，应该先检查指针本身是否为空，再访问其他成员，这样才能写出健壮，无崩溃的代码。

4.合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

之前有过合并两个有序数组的文章：数据结构：顺序表-CSDN博客，除过我文章中的，还可以通过这篇文章c语言内存函数以及数据在内存中的存储_函数在内存里是如何存储的-CSDN博客中的memcpy解决。

先理解题意：

思路一：

创建新链表，遍历并比较原链表中结点的值，小的插入到新链表。

编写代码方式一：

代码：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//创建空链表ListNode* newHead, *newTail;newHead = newTail = NULL;ListNode* l1 = list1;ListNode* l2 = list2;if(l1 == NULL){return l2;}if(l2 == NULL){return l1;}//遍历while(l1 != NULL && l2 != NULL){if(l1->val < l2->val){//l1尾插//空链表if(newHead == NULL){newHead = newTail = l1;}else{//非空newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{//l2尾插//空链表if(newHead == NULL){newHead = newTail = l2;}else{//非空newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}//遍历下去，l1为空或l2为空时if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}return newHead;
}

最终测试通过。

编写代码方式二：

上述代码有冗余，以往有联合的方式进行整合：自定义类型：联合和枚举-CSDN博客，不过此处根本原因是：初始时链表为空，那如果我创建非空链表呢？

代码如下：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//创建非空链表ListNode* newHead, *newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));ListNode* l1 = list1;ListNode* l2 = list2;if(l1 == NULL){return l2;}if(l2 == NULL){return l1;}//遍历while(l1 != NULL && l2 != NULL){if(l1->val < l2->val){//l1尾插newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{//l2尾插newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}//遍历下去，l1为空或l2为空时if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}ListNode* retHead = newHead->next;free(newHead);newHead = NULL;return retHead;
}

最终通过测试。

思路二：

使用递归，假设 “当前两个链表的剩余部分已合并为有序链表”，只需决定当前头节点的选择，递归处理剩余部分。

代码如下：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode* l1 = list1;ListNode* l2 = list2;// 基准情况：如果一个链表为空，返回另一个链表if (l1 == NULL) return l2;if (l2 == NULL) return l1;// 递归选择较小的节点作为当前节点if (l1->val <= l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}

最终通过测试。

5.链表的回文结构

链表的回文结构_牛客题霸_牛客网

本题在牛客网上，选择编程语言没有c语言，只能选c++，不过此题涉及到的也只是不需要写这串代码：typedef struct ListNode ListNode; 其余按照c语言完成即可。

理解题意：

思路一：

创建一个新链表，保存原链表所有结点，反转新链表，判断两者结点是否相同。

代码如下：

class PalindromeList {public:// 复制链表ListNode* copyList(ListNode* head) {if (head == NULL) return NULL;ListNode* copyHead = new ListNode(head->val);ListNode* curCopy = copyHead;ListNode* curOrg = head->next;while (curOrg != NULL) {curCopy->next = new ListNode(curOrg->val);curCopy = curCopy->next;curOrg = curOrg->next;}return copyHead;}// 反转链表ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* cur = head;while (cur != NULL) {ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;}bool chkPalindrome(ListNode* A) {if (A == NULL) return true; // 空链表视为回文ListNode* copy = copyList(A);ListNode* reversed = reverseList(copy);ListNode* p1 = A;ListNode* p2 = reversed;// 逐节点比较while (p1 != NULL && p2 != NULL) {if (p1->val != p2->val) {return false;}p1 = p1->next;p2 = p2->next;}return true;}
};

最终测试通过。

思路二（投机取巧）：

题中保证链表长度小于等于900即可，那么创建数组大小为900，遍历链表，将其依次存储在数组中，若数组为回文结构，那么链表也是回文结构。

代码如下：

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint arr[900] = {0};//遍历ListNode* curr = A;int i = 0;while(curr){arr[i++] = curr->val;curr = curr->next;}//判断int left = 0;int right = i - 1;while(left < right){if(arr[left] != arr[right]){return false;}left++;right--;}return true;}
};

最终测试通过。

思路三：

找到链表的中间节点，将中间节点作为新链表的头节点，反转链表，遍历原链表和反转后的链表节点是否相等。

代码如下：

class PalindromeList {public://快慢指针找中间结点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;
}//反转ListNode* reverseList(struct ListNode* head) {if (head == NULL) {return head;}//创建三个指针ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}bool chkPalindrome(ListNode* A) {// write code here//找中间节点ListNode* mid = middleNode(A);//反转ListNode* rev = reverseList(mid);//比较ListNode* left = A;while(rev){if(left->val != rev->val){return false;}left = left->next;rev = rev->next;}return true;}
};

最终测试通过。

本章完。