單鏈表反轉(zhuǎn)
很多時候工作和面試的時候都會遇到類似的單鏈表反轉(zhuǎn)的情況冀宴，今天就參考寫了一個,類似數(shù)據(jù)結構和算法的知識允瞧，最主要的不是代碼而是思路和思維方式易阳；盡管這方面我也只是很普通的一位叁幢，于是在努力進步的道路上钞馁。
實現(xiàn)的兩種方式:主要是以java形式來實現(xiàn)。
遞歸方式
反轉(zhuǎn)的本質(zhì)是指向方向比如 A->B->C->D 那么遞歸來實現(xiàn)二打，判斷如果后面還有元素县忌，那么就先讓后面的元素反轉(zhuǎn)，進而向前遞歸继效，先反轉(zhuǎn)A但是A下一個元素有B所以就先反轉(zhuǎn)B但是B下一個元素是C症杏，以此類推，最先反轉(zhuǎn)的是D. 代碼實現(xiàn)
//遞歸
public static Node reverse(Node header){
if (header == null || header.getNext() == null){
return header;
}
Node rehead = reverse(header.getNext());// 先反轉(zhuǎn)后一元素
header.getNext().setNext(header);//將當前節(jié)點指向前一節(jié)點
header.setNext(null);
return rehead;
}
非遞歸方式(遍歷方式)
我們大部分人還是正向思維瑞信，也就是平時用的比較多的遍歷思維厉颤，正向的思考，遞歸是反向的思維方式凡简，計算機科學思維使用最多的方式之一逼友。遍歷代碼實現(xiàn)如下：
public static Node reverse2(Node head) {
if (head != null) {
Node prevNode = head;//上一個節(jié)點
Node currentNode = head.getNext();//當前節(jié)點
Node tempNode;// 臨時結點，用于保存當前結點（即下一結點）
while (currentNode != null) {
tempNode = currentNode.getNext();
currentNode.setNext(prevNode);//反轉(zhuǎn)指向
//指向移動
prevNode = currentNode;
currentNode = tempNode;
}
head.setNext(null);
return prevNode;
}
return null;
}
肯定會說搞一個完整的代碼運行下就啥也明白了秤涩，是的完整代碼下面就有惋砂，還是希望讀者可以先理解思路和簡單的實現(xiàn)方式或者代碼片段筷厘，最后再用完整的代碼來看效果便于記憶嘿棘。完整代碼實現(xiàn)：
public class Node {
private String data;
private Node next;
public Node(String data,Node next){
this.data = data;
this.next = next;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public static void main(String[] args) {
Node nodeE = new Node("E",null);
Node nodeD = new Node("D",nodeE);
Node nodeC = new Node("C",nodeD);
Node nodeB = new Node("B",nodeC);
Node nodeA = new Node("A",nodeB);
Node node = nodeA;
while (node != null){
System.out.println(node.data);
node = node.getNext();
}
System.out.println("------------------------");
Node nodeW = reverse(nodeA);
while (nodeW != null){
System.out.println(nodeW.data);
nodeW = nodeW.getNext();
}
}
//遞歸
public static Node reverse(Node header){
if (header == null || header.getNext() == null){
return header;
}
Node rehead = reverse(header.getNext());// 先反轉(zhuǎn)后一元素
header.getNext().setNext(header);//將當前節(jié)點指向前一節(jié)點
header.setNext(null);
return rehead;
}
//遍歷
public static Node reverse2(Node head) {
if (head != null) {
Node prevNode = head;//上一個節(jié)點
Node currentNode = head.getNext();//當前節(jié)點
Node tempNode;// 臨時結點蔗包，用于保存當前結點（即下一結點）
while (currentNode != null) {
tempNode = currentNode.getNext();
currentNode.setNext(prevNode);//反轉(zhuǎn)指向
//指向移動
prevNode = currentNode;
currentNode = tempNode;
}
head.setNext(null);
return prevNode;
}
return null;
}
}
很多時候大家遇到問題第一件事情基本都是在找直接可以用的答案镶苞，然而大蝦或者大俠們第一個想到的是思路葛超，理解以及思維方式的鍛煉颁井。從中涉及到的知識點或者原理淫奔，如果我們也類似迷媒蚧或者懶墮的伸手黨振定，那我們也需要做出點什么改變來嘗試一下，也許會有意想不到的驚喜肉拓。以上寫法參考https://blog.csdn.net/guyuealian/article/details/51119499
后來發(fā)現(xiàn)一個更為簡潔的代碼實現(xiàn)可以參考:https://www.cnblogs.com/tina-smile/p/4878983.html
