网站开发公司 广告词,网站建设远洋国际,成都做小程序定制开发多少钱,如何设置多个首页wordpress题目描述 反转一个单链表。#xff08;题目来源#xff09; 思路一
其实#xff0c;反转一个单向链表#xff0c;我们可以看成是将链表中的每个结点的指向反向#xff08;即从后一个结点指向前一个结点#xff09;。 我们在考虑情况的时候#xff0c;还是可以先考虑一般…题目描述 反转一个单链表。题目来源 思路一
其实反转一个单向链表我们可以看成是将链表中的每个结点的指向反向即从后一个结点指向前一个结点。 我们在考虑情况的时候还是可以先考虑一般情况再考虑特殊情况。
一、一般情况
我们如果直接让后一个结点指向前一个结点那么后一个结点所指向的再后面的结点的位置就无从知晓了因此我们定义3个指针变量n1,n2,n3。
n1记录指针指向将要反转的结点反转后要指向的结点。
n2记录指针指向将要反转的结点。
n3记录指针指向将要反转的下一个结点。 在反转时首先让n2指向的结点指向n1指向的位置然后让n1,n2,n3指针统一后移准备执行下一对结点之间指向的反转。 如此进行下去所有结点指向都将反转。
二、极端情况
1.传入的链表为空时
若为空直接返回头指针即可。
若传入链表只有一个结点同上。
2.反转第一个结点指针的指向 因为在我们反转的过程中就是让n2指向的结点指向n1指向的位置所以我们只需将n1的初始值赋值为NULL即可。
3.反转最后一个结点指针的指向 此时发现了遍历链表的终止条件和需要返回的新的头指针即当n2指针为NULL时停止遍历并且返回n1指针指向的位置。但是这时这三个指针统一后移时n3指针的后移将失败因为n3后移前指向的是NULL所以不能执行以下这句代码。
n3 n3 - next;
所以后移n3指针前需判断其是否为空。
代码实现
struct ListNode {int val;struct ListNode* next;
};struct ListNode* reverseList(struct ListNode* head)
{if (head NULL || head-next NULL)//当链表为空或只有一个结点时无需操作return head;//直接返回struct ListNode* n1 NULL;//记录指针指向将要反转的结点反转后要指向的位置。struct ListNode* n2 head;//记录指针指向将要反转的结点。struct ListNode* n3 head-next;//记录指针指向将要反转的结点的下一个结点。while (n2)//n2为NULL时停止遍历{n2-next n1;//反转结点指向n1 n2;//指针后移n2 n3;//指针后移if (n3)//判断n3是否为NULLn3 n3-next;//指针后移}return n1;//返回n1指针指向的位置
}
思路二
将原链表的结点从头到尾一个个地拿下来头插到一个新链表中这个新链表起始为一个空链表newhead指向NULL。 代码实现
struct ListNode {int val;struct ListNode* next;
};struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;//记录当前待头插的结点struct ListNode* newhead NULL;//新链表初始时为空while (cur)//链表中结点头插完毕时停止循环{struct ListNode* next cur-next;//记录下一个待头插的结点cur-next newhead;//将结点头插至新链表newhead cur;//新链表头指针后移cur next;//指向下一个待头插的结点}return newhead;//返回反转后的头指针
}
