以下题目源于LeetCode
一、反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000来源：力扣（LeetCode）
链接：206. 反转链表
思路1：
做题，一定要画图，不然你的逻辑思维容易混乱，经常一跑起来都是bug，思维错误。
现在是想将链表倒转过来，
我们首先把1当作尾节点指向NULL，之后再将2指向1，重复到5指向4
但是单链表是不可逆，我们把1指向NULL时，接下来如何找到2呢？
所以我们要创建一个变量，存储它下一个节点
总共定义三个变量
prev ：（previous）前一个
cur：（current）当前的
next：下一个
我们不要随便命名，每个变量最好的名字都是他们所代表的东西，让自己和别人都容易理解
我们要将cur指向prev作为尾节点，，之后这三个变量都往后移一位
循环往复，直到prev走到5了，那我们是不是就成功了呢？
走到5我们的逻辑图应该时这样的，这时候我们应该注意到next的位置，是存在问题的，所以在编写代码的时候要注意到
核心逻辑：
将cur指向prev
prev，cur，next各向后走一位
循环条件：
当cur不为NULL的时候
需要注意：
next为空之后不能继续解引用
传递空指针应该如何应对
struct ListNode* reverseList(struct ListNode* head){ if(head == NULL) //防止空指针 { return NULL; } struct ListNode* prev = NULL; struct ListNode* cur = head; struct ListNode* next = head->next; while(cur) { cur->next = prev; prev = cur; cur = next; if(next) //当next已经走到NULL的时候 不再向后走否则无法解引用 { next = next->next; } } return prev; }
思路2：
利用我们之前讲过的头插，创建一个新的变量值为NULL，将1，2，3，4，5元素插入新变量中
还是需要三个新变量:
struct ListNode* newnode = NULL;
struct ListNode* cur = head;
struct ListNode* next= cur->next;
每次将cur前插入到newnode中也就是刚开始创建的NULL
之后cur的值变为next，next是cur的后一位
struct ListNode* reverseList(struct ListNode* head){ if(head == NULL) { return NULL; } struct ListNode* newnode = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next= cur->next; //确保每次next都是cur的下一个节点 cur->next = newnode; //将开头指向新的链 newnode = cur; //新链的头指向刚加入的cur cur = next; //cur后移一位 } return newnode; }
二、链表的中间节点
难度简单725收藏分享切换为英文接收动态反馈
给定一个头结点为
head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。提示：
- 给定链表的结点数介于
1和100之间。来源：力扣（LeetCode）
链接：876. 链表的中间结点
解析一下这道题，找到中间节点，如果有两个中间节点取第二个
第一种方法：
我最开始想的是遍历找到尾节点，求出长度length，之后头节点向后移动length/2+1次，就能求出中间节点，但是这样的时间复杂度是O(n)，操作起来也比较麻烦。
这个感兴趣的可以自己去动手实现
第二种方法：
这道题是打开我们一个新思路的大门，很简单，但是像我这种初学者不容易想到
我们需要快慢指针，这也是我首次接触到这种方法，确实很巧妙
来画图演示一下：
定义一个slow指针和fast指针，slow每一次后移一位，fast每次后移两位
无论是有一个中间节点，还是两个中间节点，我们都能准确地找到我们所需要的那一个
根据图我们可以判断出当fast为NULL时和fast->为NULL时，我们的slow就找到了中间节点
所以我们的循环语句判断条件为(fast != NULL && fast -> next != NULL)
避免空指针解引用！！！！！（哥们在这吃老亏了 -^-）
一定要避免空指针的解引用，所以上面两个判断条件的位置不能调换！
fast如果时NULL时，就不会去判断fast->next是否为NULL，避免了空指针解引用。
struct ListNode* middleNode(struct ListNode* head) { if(head == NULL) //防止传递空指针 { return NULL; } struct ListNode* slow = head; //慢指针 struct ListNode* fast = head; //快指针 while(fast != NULL && fast->next!=NULL) //判断条件 { slow = slow->next; //slow每次后移一位 fast = (fast->next)->next; //fast每次后移两位 } return slow; }
三、链表中倒数的第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源：力扣（LeetCode）
链接：链表中倒数的第k个节点
遍历的方法我们就不提了
这道题的解题方法还是快慢指针，不过不同的是
fast先走k步，之后fast与slow同时走，直到fast为
虽然单链表不知道倒着走，但是我让一个指针先走k步当这个指针走到尾另一个指针再走，那么后走的指针就与结尾差k
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
int i = 0;
for(i = 0; i < k; i++)
{
fast = fast->next;
}
while(fast !=NULL)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}四、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：输入：l1 = [], l2 = []
输出：[]
示例 3：输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列来源：力扣（LeetCode）
链接：合并两个有序链表
接下来是我自己的想法，还没听老师讲的，有点多，不知道是否有些地方存在冗余
想法：创建一个新的节点接收，将每一个小的元素尾插
/**
* 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;
}
//定义指针指向当前位置，和一个newnode来存放新链作为返回值
struct ListNode* head1 = list1;
struct ListNode* head2 = list2;
struct ListNode* newnode = NULL;
//首先newnode现在存放的还是一个空指针，我们要将一个节点放进去以防后面空指针解引用
if(head1->val > head2->val)
{
list2 = list2->next;
newnode = head2;
head2->next = NULL;
}
else
{
list1 = list1->next;
newnode = head1;
head1->next = NULL;
}
//创建一个尾节点，在尾插时好指向比较出较小的节点
struct ListNode* tail = newnode;
//假如有个链到尾了就结束
while(list1 && list2)
{
head1 = list1;
head2 = list2;
if(head1->val > head2->val)
{
list2 = list2->next;
tail->next = head2;
tail = head2;
head2->next = NULL;
}
else
{
list1 = list1->next;
tail->next = head1;
tail = head1;
head1->next = NULL;
}
}
//假如有个链表先走完了，将另一个链表直接尾插到newnode后面
if(list1 == NULL)
{
tail->next = head2;
}
else
{
tail->next = head1;
}
return newnode;
}
图片太多了所以就不画了，原理还是很简单的，自己动手画一下
老师的方法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1==NULL)
{
return l2;
}
if(l2 == NULL)
{
return l1;
}
struct ListNode* head = NULL,*tail = NULL;
if(l1->val<l2->val)
{
head = tail = l1;
l1 = l1->next;
}
else
{
head = tail = l2;
l2 = l2->next;
}
while(l1 && l2)
{
if(l1->val < l2->val)
{
tail->next = l1;
tail = l1;
l1 = l1->next;
}
else
{
tail->next = l2;
tail = l2;
l2 = l2->next;
}
}
if(l1)
{
tail->next = l1;
}
if(l2)
{
tail->next = l2;
}
return head;
}
大家还是分析一下老师的方法，我和老师的大体思路一样，但是老师的优化很好。