力扣 206反轉連結清單

反轉一個單連結清單。

示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

1.利用外部條件 容器

一開始想到的就是這種方法

具體實作就是想連結清單放進容器中，利用容器的函數完成操作

也可以用棧，将元素壓棧，利用棧先進後出的特性，将頭指針依次指向出棧節點。

代碼：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<ListNode *>s;
     
        for(ListNode *p=head;p;p=p->next)//入棧 從頭結點開始入
        {
            s.push(p);
        }
        ListNode *l=new ListNode(-1);//建立新表的預先指針 也可以在原表基礎上建 但是沒成功 l不動
        ListNode *cur=l;//目前指針 動
        while(!s.empty())
        {
           // cur->next=new ListNode(0);
            cur->next=s.top(); //指向棧頂元素 
            cur=s.top();//指針下移 棧頂是表尾，棧底是表頭所有這樣表示
            s.pop();//出棧
        }
        cur->next=NULL;//尾指向空
        return l->next;//傳回頭結點
    }
};
           

2.雙指針 疊代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p=NULL;//新表首結點，初始化為null，使新表指向null
       ListNode *next=NULL;//下一個元素
       while(head)
       {
           next=head->next;//下一個結點
           head->next=p;//目前結點連結p p=null，則将這個結點摘出
           p=head;//p指向目前結點，目前結點成為新表首結點
           head=next;//head指向舊表的下一個結點
           
       }
       return p;
    }
};
           

圖解：http://www.pianshen.com/article/517476376/

3.遞歸

假設清單的其餘部分已經被反轉，現在我該如何反轉它前面的部分？

清單nk-2 nk-1 nk nk+1 nk+2 。。。。

正處于nk若反轉 使nk+1指向nk 則需

head->next->next=head;

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        ListNode *p=reverseList(head->next);
       head->next->next=head;
       head->next=NULL;
       return p;
    }
};
           

三種方法整體效率對比：基本沒差