題目信息
問題：如何實現(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é)點接受反轉
// 找到倒數(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é)點接上反轉
lastNode->next = reverseList(head);
return lastNode;
}
- Java語言代碼利用了棧結構后進先出的特點實現(xià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;
}
}
總結
遞歸與棧結構兩種的空間復雜度都比較低，但是時間復雜度很高琳猫。
網(wǎng)友們有更加好的方法伟叛，值得學習。
