題目信息
問題：如何實現(xiàn)一個高效的單向鏈表逆序輸出？
出題人：阿里巴巴出題專家：昀龍／阿里云彈性人工智能負責人
代碼
分別用C語言和Java完成了該題目，題目在Leetcode上難度是簡單。
- C語言代碼采用的是遞歸法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
// 特殊情況, 原樣返回
if (head == NULL || head->next == NULL) {
return head;
}
// 該題使用遞歸的方法
// 找到最后一個節(jié)點，作為新的頭
// 而其他的節(jié)點接受反轉(zhuǎn)
// 找到倒數(shù)第二個節(jié)點和最后一個節(jié)點
struct ListNode* curr = head;
struct ListNode* lastNode;
struct ListNode* lastSecondNode;
while (curr != NULL) {
// 最后一個節(jié)點
if (curr->next == NULL) {
lastNode = curr;
}
// 倒數(shù)第二個節(jié)點
else if (curr->next->next == NULL) {
lastSecondNode = curr;
}
curr = curr->next;
}
// 倒數(shù)第二個節(jié)點后面接 NULL， 作為最后一個節(jié)點
lastSecondNode->next = NULL;
// 遞歸部分 最后一個節(jié)點接上反轉(zhuǎn)
lastNode->next = reverseList(head);
return lastNode;
}
- Java語言代碼利用了棧結(jié)構(gòu)后進先出的特點實現(xiàn)了鏈表的反轉(zhuǎn)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 特殊情況
if (head == null || head.next == null) {
return head;
}
// 用棧來做這題
Stack<ListNode> stack = new Stack<>();
// 將所有節(jié)點壓入棧
ListNode curr = head;
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
// 最后一個節(jié)點作為新的頭
ListNode newHead = stack.peek();
while (!stack.isEmpty()) {
// 指針指向彈出的節(jié)點
ListNode node = stack.pop();
// 彈出后?？樟? if (stack.isEmpty()) {
node.next = null;
}
else {
node.next = stack.peek();
}
}
// 返回新的 head
return newHead;
}
}
總結(jié)
遞歸與棧結(jié)構(gòu)兩種的空間復(fù)雜度都比較低，但是時間復(fù)雜度很高。
網(wǎng)友們有更加好的方法，值得學(xué)習(xí)。
