1.反转链表
解题： 方法一 和 方法二
方法一：****将原链表中，各个节点链接的方向反转。
（图解中可以看出原空间位置并没有发生改变 ，而是要改变每个节点中存储的指针指向 。）
实现细节：
** 1.保留本次节点：**
** 每次遍历到下一个位置前，要将这次遍历的节点地址保存下来，方便后节点指向前节点 。**
** 2.预保留下一个节点：**
** 因为每次遍历后，当前节点将不会指向原始的后节点 ，而是指向前节点（因为要逆序）， 所以为了下次遍历能够找到后节点 ，请先将后节点的地址保存下来 。**
** 3.结束条件为：预保留的下一个节点为空指针，说明遍历完成 。**
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
if(head) //防止传入空指针
{
ListNode *Last = NULL;
ListNode *Next = head->next;
for(;Next;)
{
Next = head->next; //保存下一个节点
head->next = Last; //改变原指向
Last = head; //保存上一个节点
if(Next) //下一个节点如果NULL说明遍历完成
head = Next;
}
}
return head;
}
方法二： 新空间倒放 ， 建立一个新空间 ，将原空间的数据
**从新空间的尾部开始，依次向新空间的头部存放。**
实现细节：
** **** 1.****每次循环需要创建一块新节点 **
** **** 2.**每次创建的新节点都是从新链表的尾部向头部创建 。
** **** 3.**返回新空间的地址
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* New = head;
if (head && head->next) //当原链表为空或只有一个元素时，无需逆序
{
ListNode* last = NULL; //置为空，因为首次创建的新节点是整个新空间的尾节点
for (; head; head = head->next)
{
New = (ListNode*)malloc(sizeof(ListNode)); //每次循环创建一块新节点
New->val = head->val; //将原空间的数据存入新节点
New->next = last;
last = New; //将本次创建的新节点地址保留
}
}
return New;
}
2.找中间节点
- 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/middle-of-the-linked-list/
解题：
方法一 ：快慢指针，利用双指针，其中快指针遍历两个节点，慢指针遍历一个节点，当快指针走 完整个链表时，慢指针走完半个链表，其位置为中间节点。
实现细节：
** 1. 因为位数的奇或偶时，有两种情况：（这里建议要自己画图模拟一遍就清楚了）**
** 奇数 ：快指针正好遍历完一遍数组，并且不会越界，**
** 偶数 ：如果不加制约，快指针会越界**
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
for(;fast->next&&fast->next->next;) //这里设定两种情况，因为位数不确定
{
fast = fast->next->next;
slow = slow->next;
}
if(fast->next) //判断是奇数位还是偶数位
{
return slow->next;
}
return slow;
}
3.输入倒数第K个节点
链表中倒数第k个结点_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
解题：方法一 ， 和 方法二
方法一：利用一前一后双指针（快慢指针的变式），两指针之间始终相差K个数据，当后指针遍历完成时，前指针正好位于尾节点前第K个位置 。
实现细节 （主要是判断K）:
** 1. 传入指针为NULL 或k = 0 ：返回NULL;**
** 2. k 的值大于数据个数：需要进行判断 ，思想在代码中有解释 ，而且判断后**
** 正好还实现了前后指针的位置差（真的很妙) ;**
typedef struct ListNode ListNode;
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
if(pListHead&&k)
{
ListNode* tem = pListHead;
for(;k>0;k--,pListHead = pListHead->next) //判断是否越界
{
if(pListHead); //正常情况：pListHead 正好为空 或不为空
else //不正常情况：如果，在pListHead为空又执行
return NULL; //循环，说明 K 的值 大于 数据个数
}
for(;pListHead;)
{
pListHead = pListHead->next;
tem = tem->next;
}
return tem;
}
return NULL;
}
**方法二：（嘿嘿，小白博主自己想的） **
倒数第K个，就是从尾节点正数 第K个，所以先把链表逆序，然后正数，返回，但是他居然既要返回节点，还要节点后的序列为正常顺序；所以在吧节点后的序列再逆序回来 。
（这做法，很冗余，看看就行了哈）
typedef struct ListNode ListNode;
struct ListNode* FindKthToTail(struct ListNode* pphead, int k ) {
// write code here
if (k && pphead)
{
struct ListNode* Next, * last;
last = NULL;
for (; pphead->next; pphead = Next)
{
Next = pphead->next;
pphead->next = last;
last = pphead;
}
pphead->next = last;
struct ListNode* tem = pphead;
for (; k > 1 && pphead; k--)
{
pphead = pphead->next;
}
last = NULL;
if (pphead)
{
for (; tem != pphead; tem = Next)
{
Next = tem->next;
tem->next = last;
last = tem;
}
pphead->next = last;
}
}
else
{
pphead = NULL;
}
return pphead;
}
4.合并两个有序链表
解题：方法一（建立新节点）和 方法一小变式（不建立新节点）
方法一：建立一个新头节点（相当于一个哨兵位），然后将两个链表中的数据依次比较，
** 并将较小的数据所在节点，与新头节点链接起来，组成由新头节点带头的新链表。**
实现细节：
** 1.哪个表传入节点，哪个表就向下遍历，没传入节点的表不要动。**
** 2. 当一个链表先传入完毕，就直接将另一个链表的剩余节点全部链接在新链表后就行了 。 （因为是两个升序链表，一个传完，说明剩下数据的都比前面的大）**
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//创建新头节点 ，新头节点是用来存储下一个传入节点的位置的，所以无需对val赋值
ListNode* tem = (ListNode*)malloc(sizeof(ListNode));
ListNode* tem1 = tem; //tem1用来记录新头节点位置
for(;list1&&list2;) //判断是否传入NULL
{
if(list1->val<=list2->val) //比较两表中数据
{
tem->next = list1; //此时传入list1
list1 = list1->next; //list1就向下遍历
}
else
{
tem->next = list2; //此时传入list2
list2 = list2->next; //list2就向下遍历
}
tem = tem->next; //传入新节点后，新表向下遍历
}
if(list1) //如果list1没传完
tem->next = list1; //就直接链接剩余list1
else
tem->next = list2; //同上
return tem1->next;
}
方法一小变式：不建立新节点，在开始时就将list1和list2 的头节点数据进行比较，
** 然后将两表中小的数据节点，作为头节点，其余不做变动。**
** （但是在具体实现上要进行更多的NULL判断，就不详细说了哈，有需要的可以看看）**
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
ListNode* tem = NULL;
ListNode* tem1 = tem;
if(list1&&list2)
{
if(list1->val<=list2->val)
{
tem = list1;
list1 = list1->next;
}
else
{
tem = list2;
list2 = list2->next;
}
tem1 = tem;
}
for(;list1&&list2;)
{
if(list1->val<=list2->val)
{
tem->next = list1;
list1 = list1->next;
}
else
{
tem->next = list2;
list2 = list2->next;
}
tem = tem->next;
}
if(tem&&list1)
{
tem->next = list1;
return tem1;
}
else if(tem)
{
tem->next = list2;
return tem1;
}
else
if(list1)
return list1;
return list2;
}
5.移除链表元素
** 解题：方法一：正常遍历，遇到要删除的元素就将前后两个节点链接（相当于跳过该节点）**
** 实现细节：1.要用两个指针保留前后两个节点**
** 2.如果要删除头节点，每次删除的同时，要相应的改变起始位置**
** 3.假设用来保留前节点的指针Last，Last一定要指向不删除的节点 。**
** 因为是将前后两个都不删除的元素保留，如果连续删除时，不对Last进行约束，**
** Last会将要删除的元素保留下来。**
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
ListNode* tem = head; //保留起始位置
ListNode* Last = head; //保留前一个节点
ListNode* Next = head; //保留下一个节点
for(;head;head = Next )
{
Next = head->next;
if(head == tem&&head->val == val)//判断是否删除节点
{
tem = Next; //改变起点
}
else if(head->val == val)
{
Last->next = Next; //正常删除
}
if(head->val != val) //避免连续删除时Last保留要删除元素
Last = head;
}
return tem;
}
感谢观看！！！（小白博主有写的不对或不好的地方，请各位大佬指教）
版权归原作者 MT_125 所有， 如有侵权，请联系我们删除。