大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章为大家分享实现翻转链表的一道算法题。文章这道题使用了递归和栈等方法实现翻转链表,希望大家通过这篇文章能有所收获。
创新互联专注为客户提供全方位的互联网综合服务,包含不限于网站设计制作、成都网站设计、凤庆网络推广、重庆小程序开发、凤庆网络营销、凤庆企业策划、凤庆品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;创新互联为所有大学生创业者提供凤庆建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com每K个节点一组进行翻转,剩下不足K个的保留原状.
将链表分成三部分,已翻转,待翻转,未翻转三部分:
首先,用一个指针t表示要插入的位置的前驱,一边把head移动k遍,一边插入在t后面(下图假设k=3):
int i=0;
for(;i
直接插在t的后面,一轮循环之后,移动t与head.
t的新位置为未插入head之前的head的位置,因此在插入之前把head的位置保存下来,直接使t移动到该位置,head的位置为自然移动到的位置,不需改变。
ListNode nextTPosition = head;
ListNode temp;
int i=0;
for(;i
接着再翻转,到达7后,7不需要翻转,因为剩下的节点数不足:
这时就需要i发挥作用了,i表示已翻转的节点的值,因为只是一次遍历,每遍历k次便翻转k次,若i小于k,由于已经翻转了剩下的i个节点,因此需要再将这剩下的i个节点翻转一次:
if(i == k)
t = nextTPosition;
else
{
for(head = t.next,t.next=null;head!=null;)
{
temp = head.next;
head.next = t.next;
t.next = head;
head = temp;
}
break;
}
对剩下的i个节点再次翻转时,不需要修改t的位置,使head指向t.next,再把t.next置为null,因为此时t为
4->7
若不把t.next置为null,在
head.next = t.next
这一步会使head.next指向错误的t.next,导致会在最后一个节点不断循环。
翻转最后的i个节点后,跳出循环,返回结果。
递归的话思路也类似,遍历k次,翻转k个,若还有需要翻转的节点,递归翻转,若没有,翻转剩下的i个节点。
if(i == k)
t.next = reverse(head,k);
大部分代码与循环相同就不贴了,大的不同是这里,这里的t为原来未遍历前的head,因为改成递归后,不需要使用t作为移动的指针指示插入的位置,t.next就相当于翻转后的最后一个节点,把递归的结果插入到这个节点的后面。
因为题目规定只能使用常数的额外空间,因此应该只有这两种方法了,但是,如果允许使用额外的空间,可以使用栈优化直接翻转的算法。
因为出栈的次序正是翻转的顺序,每遍历k个节点就压栈k个节点,若剩余不足k个节点,把head连上dummy,若还有多余的节点或者刚好遍历完,把出栈的节点依次连上主链。
while(true)
{
Stack s = new Stack<>();
ListNode temp = head;
int i=0;
for(;i
其中for循环为遍历压栈,i==k判断是否翻转链表。
关于实现翻转链表就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果喜欢这篇文章,不如把它分享出去让更多的人看到。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。