递归和非递归方式反转单向链表的使用方法

来源:爱站网时间:2020-03-14编辑:网友分享
在学习C语言的时候我们会使用到递归和非递归方式反转单向链表,但是有很多小伙伴们不知道如何使用递归和非递归方式反转单向链表的,那么下面我们就去看看递归和非递归方式反转单向链表的使用方法。

在学习C语言的时候我们会使用到递归和非递归方式反转单向链表,但是有很多小伙伴们不知道如何使用递归和非递归方式反转单向链表的,那么下面我们就去看看递归和非递归方式反转单向链表的使用方法。

问题:
给一个单向链表,把它从头到尾反转过来。比如: a -> b -> c ->d 反过来就是 d -> c -> b -> a 。

分析:
假设每一个node的结构是:

 

class Node {
 char value;
 Node next;
}


因为在对链表进行反转的时候,需要更新每一个node的“next”值,但是,在更新 next 的值前,我们需要保存 next 的值,否则我们无法继续。所以,我们需要两个指针分别指向前一个节点和后一个节点,每次做完当前节点“next”值更新后,把两个节点往下移,直到到达最后节点。

代码如下:

 

 

 


public Node reverse(Node current) {
 //initialization
 Node previousNode = null;
 Node nextNode = null;

 while (current != null) {
  //save the next node
  nextNode = current.next;
  //update the value of "next"
  current.next = previousNode;
  //shift the pointers
  previousNode = current;
  current = nextNode;   
 }
 return previousNode;
}


上面代码使用的是非递归方式,这个问题也可以通过递归的方式解决。代码如下:

 

 

 


public Node reverse(Node current)
 {
     if (current == null || current.next == null) return current;
     Node nextNode = current.next;
     current.next = null;
     Node reverseRest = reverse(nextNode);
     nextNode.next = current;
     return reverseRest;
 }


递归的方法其实是非常巧的,它利用递归走到链表的末端,然后再更新每一个node的next 值 (代码倒数第二句)。 在上面的代码中, reverseRest 的值没有改变,为该链表的最后一个node,所以,反转后,我们可以得到新链表的head。

上文中小编详细介绍了递归和非递归方式反转单向链表的使用方法,有需要的用户,可以参照上述操作哦,希望今天的分享能给大家带来帮助。

上一篇:C++中的友元函数的总结

下一篇:c调用python出现异常怎么办

您可能感兴趣的文章

相关阅读

热门软件源码

最新软件源码下载