經(jīng)歷了很多面試，面試官考察的算法無非是斐波那契數(shù)列和單鏈表反轉(zhuǎn)，盡管是這些都是基礎(chǔ)知識(shí)，然而我對(duì)單鏈表反轉(zhuǎn)有更多的想法。
遞歸法是我早期在面試中使用的算法，很有逼格，寫起來非常優(yōu)雅，非常好理解。
先定義鏈表數(shù)據(jù)結(jié)構(gòu)
static class Node {
Integer data;
Node next;
}
static Node readyNode() {
Node linkNode1 = new Node();
linkNode1.data = 1;
Node linkNode2 = new Node();
linkNode2.data = 2;
Node linkNode3 = new Node();
linkNode3.data = 3;
Node linkNode4 = new Node();
linkNode4.data = 4;
Node linkNode5 = new Node();
linkNode5.data = 5;
Node linkNode6 = new Node();
linkNode6.data = 6;
linkNode1.next = linkNode2;
linkNode2.next = linkNode3;
linkNode3.next = linkNode4;
linkNode4.next = linkNode5;
linkNode5.next = linkNode6;
return linkNode1;
}
如上代碼所示
static Node reverseLinkedList(Node node) {
if (node == null || node.next == null) {
return node;
} else {
Node headNode = reverseLinkedList(node.next);
node.next.next = node;
node.next = null;
return headNode;
}
}
上圖展示了遞歸后的效果。
如果注釋掉第7行，會(huì)發(fā)生如上圖所示的1、2號(hào)節(jié)點(diǎn)閉環(huán)問題。由于1號(hào)節(jié)點(diǎn)的next沒有置空，依舊指向2號(hào)節(jié)點(diǎn)，所以遍歷時(shí)候肯定存在環(huán)。
static Node reverseLinkedList(Node node) {
Node previousNode = null;
Node currentNode = node;
Node headNode = null;
while (currentNode != null) {
Node nextNode = currentNode.next;
if (nextNode == null) {
headNode = currentNode;
}
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = nextNode;
}
return headNode;
}
LinkedList的反轉(zhuǎn)
LinkedList沒有提供反轉(zhuǎn)鏈表的相關(guān)函數(shù)，以下是通過foreach實(shí)現(xiàn)鏈表反轉(zhuǎn)
static LinkedList reverseLinkedList(LinkedList linkedList) {
LinkedList<Object> newLinkedList = new LinkedList<>();
for (Object object : linkedList) {
newLinkedList.add(0, object);
}
return newLinkedList;
}
想要知道更多的java應(yīng)用技術(shù)那就加入我們吧！