意思就是把链表尾当成链表头,并且每个节点的指针反向。先看下图:
黑色部分是原来链表;红色部分是翻转后的链表。思路分析:1、拿到head链表头,然后递归处理。2、当处理到head节点是,需要把head的next指针置空。3、如果是最后一个节点,需要把节点引用赋给head。4、如果是中间的某节点,需要把其引用赋给他下一个节点的next指针。思路理清楚了,感觉好像不难。我们开始撸代码。
public void reserve(Node node){ //1 if(node == null){ //当前节点为null return; } //2 if(node == head){ //如果是head节点 head.next = null; } //3 if(node.next == null){ //末尾节点 head = node; return; } //4 //获取下一个节点 Node nextNode = node.next; //翻转,下一个节点的next指针指向当前node节点 nextNode.next = node; reserve(nextNode); }分析上面2和3处的代码, 第一次调用时,传入head节点,然后就立即执行了head.next = null; 接着就会进入3处的判断。然后程序结束了? 这儿肯定有问题,head.next不应该先处理,可以放到判断3处。修改代码如下 public void reserve(Node node){ //1 if(node == null){ //当前节点为null return; } //2.表示是末尾节点 if(node.next == null){ //先置空旧的head的next指针 head.next = null; //把末尾节点赋给head head = node; return; } //4 //获取下一个节点 Node nextNode = node.next; //翻转,下一个节点的next指针指向当前node节点 nextNode.next = node; reserve(nextNode); }代码撸完了,是不是上面这样的? 哈哈,有问题。为啥?你代入head节点看看。 会不会出现下面这张图的效果?已经是死循环了,第三个节点后面的数据都弄丢了。我们总的思路没错,但是每次都需要保存好下一个和下下一个节点。于是修改代码:
public void preReserve(Node node){ if(node == null || node.next == null){ //如果当前链表头为null,或者无下一个节点。则不需要翻转 return; } reserve(node, node.next); } private void reserve(Node curNode, Node nextNode){ //1 if(curNode == null){ //当前节点为null return; } //2.表示是末尾节点 if(nextNode == null){ //先置空旧的head的next指针 head.next = null; //把末尾节点赋给head head = curNode; return; } //4 //获取下下一个节点 Node nextNextNode = nextNode.next; //翻转,下一个节点的next指针指向当前node节点 nextNode.next = curNode; reserve(nextNode, nextNextNode); }这回是真的撸完了, Node nextNextNode = nextNode.next; 上面这行代码很重要。 你可以运行看看效果。 以上是我个人的思路,若你有更好的算法,欢迎留言