目录

• 前言
• 问题介绍
• 解决方案
• 代码编写
• • java语言版本
  • c语言版本
  • c++语言版本
• 思考感悟
• 写在最后

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神的书让我对算法有了新的感悟认识！

问题介绍

原问题
找到单链表和双向链表的倒数第k个元素并删除返回

解决方案

问题一：
1、需要一个临时变量存储下一个节点
2、当前两个节点进行翻转后，在对下一组进行翻转即可
问题二：
1、和问题一解决方式相同，多了一个前节点的变更
问题三：
1、需要注意from为头结点的问题
2、需要获取from节点的前一个节点和to节点的后一个节点
3、剩下的翻转即可

代码编写

java语言版本

public class ReverseListNode {/*** 翻转部分单链表* @param head* @param from* @param to* @return*/public static LinkNode reverseNodesFromTo(LinkNode head, int from, int to){int length = 0;LinkNode cur = head;LinkNode pre = head;LinkNode fromNode = null;LinkNode toNode = null;while (cur != null){length ++;if (length+1 == from){// from的前一个pre = cur;}if (length == from){fromNode = cur;}if (length == to){toNode = cur;}cur = cur.getNext();}if (fromNode == null || toNode == null){return null;}LinkNode toNext = toNode.getNext();if (fromNode == head){if (toNext == null){return reverse(fromNode);}else {toNode.setNext(null);reverse(fromNode);fromNode.setNext(toNext);head = toNode;}}else {toNode.setNext(null);reverse(fromNode);pre.setNext(toNode);fromNode.setNext(toNext);}return head;}/*** 翻转单链表* @param head* @return*/public static LinkNode reverse(LinkNode head){if (head == null || head.getNext() == null){return head;}LinkNode cur = head;LinkNode next = head.getNext();while (next != null){LinkNode tem = next.getNext();next.setNext(cur);cur = next;next = tem;}head.setNext(null);head = cur;return head;}/*** 翻转双链表* @param head* @return*/public static DoubleNode reverseD(DoubleNode head){if (head == null || head.getNext() == null){return head;}DoubleNode cur = head;DoubleNode next = head.getNext();// 先做这一步head.setLast(head.getNext());while (next != null){DoubleNode tem = next.getNext();next.setNext(cur);next.setLast(tem);cur = next;next = tem;}head.setNext(null);head = cur;return head;}public static void main(String[] args) {//ReverseListNode reverseListNode = new ReverseListNode();LinkNode linkNodeListByArr = CommonUtils.getLinkNodeListByArr(new int[]{5, 2, 4, 6, 7});LinkNode reverse = reverse(linkNodeListByArr);System.out.println(reverse);//DoubleNode doubleNodeListByArr = CommonUtils.getDoubleNodeListByArr(new int[]{5, 2, 4, 6, 7});//DoubleNode lastKDoubleNode = reverseD(doubleNodeListByArr);//System.out.println(lastKDoubleNode.getValue());}
}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、怎么想到的？
链表基本翻转不需要思路
2、关键逻辑
这里刚开始容易先改了节点的next后又获取next节点导致next不是自己想要的那个next节点而出错，这里避免的方式就是
先获取到next给临时变量存储，然后操作现节点，之后需要next时直接使用存储变量tem即可
3、以后遇到什么样的题用这种思维考虑？
我认为链表中最容易犯的错误就是更改了链表的next之后忘记了，之后再想获取链表的next就获取不到了导致错误的发生，这里思路可以在
图纸中先笔画一下步骤，然后将单元步骤中所用到的节点全部都用临时变量先获取出来之后再变更节点的next。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可咨询2260755767@qq.com或在评论区回复即可.
再次感谢左大神的书对我算法的指点迷津！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！