链表|关于链表的经典OJ题 leetcode|蓝桥杯|算法|数据结构

文章图片
表锅，我出来了哦！！！
表锅，表集，表die，表美们，看我金天又给大噶带来了什么咧？？？
------------额，金天给大家伙带来了，关于链表的三大经典OJ题哦！（哈哈哈哈哈哈）

1.反转单链表：https://leetcode-cn.com/problems/reverse-linked-list/
2.链表的中间结点：https://leetcode-cn.com/problems/middle-of-the-linked-list/
3.合并两个有序链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/

注：这些题都在来自力扣，大家可以复制链接直接进去答题哦！！！

文章图片

接下来，让我们进入今天的学习吧！！！
1.反转单链表：请你反转链表，并返回反转后的链表。
例图：

文章图片

文章图片
思路一：

文章图片

疑问1：为什么不是n3==NULL停止循环了？？？

文章图片

疑问2：要是链表为空了
答：要是链表为空了，直接返回NULL
注：重复的过程一般是用循环解决
【链表|关于链表的经典OJ题】循环三要素：初识值，迭代过程，结束条件
思路一代码实现：

? /** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head){ if(head==NULL) return NULL; //初始化 struct ListNode* n1 = NULL,*n2 = head,*n3 = n2->next; //结束条件 while(n2) { //迭代过程（重复过程） n2->next = n1; n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; }?

文章图片
思路二：头插法

文章图片

思路二代码实现：

/** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head){ if(head==NULL) { return NULL; } struct ListNode *cur = head,*next = cur->next; struct ListNode* newhead = NULL; while(cur) { cur->next = newhead; newhead = cur; cur = next; if(next) next = next->next; } return newhead; }

2.链表的中间结点：
给定一个头结点为head的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
例1:输入【1,2,3,4,5】输出：3
例2：输入【3,4,5,6】输出：5
思路：

文章图片

大家从上面的思路中也可以看出它也是迭代的过程，初始条件是slow，fast都指向第一个结点，迭代过程，slow走一步，fast走两步，结束条件fast->next,fast只要有一个为空就结束。
代码：

/** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */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; }

3.合并两个有序链表：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

文章图片

/** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode *head = NULL,*tail = NULL; while(list1 != NULL && list2 != NULL) { if(list1->val < list2->val) { if(tail == NULL) { head = tail = list1; } else { tail->next = list1; tail = tail->next; } list1=list1->next; } else { if(tail == NULL) { head = tail = list2; } else { tail->next = list2; tail=tail->next; } list2=list2->next; } } if(list1) { tail->next = list1; } if(list2) { tail->next = list2; }return head; }

表锅，表集，表die，表美们今天就到这里了哦！！！