反轉單連結清單 （三種方法整理）

題目：反轉單連結清單

輸入一個連結清單，反轉連結清單後，輸對外連結表的所有元素。

據找工作的師兄說，反轉單連結清單基本各個公司面試都會有，整理出一些寫的比較好的code,供我等小白們學習。

方法一

• 正常思路，簡潔，清晰，我覺得寫得蠻好的。

思路就是： 從原連結清單的頭部一個一個取節點并插入到新連結清單的頭部

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* newh = NULL;
        for(ListNode* p = pHead; p; )//p為工作指針
        {
            ListNode* tmp = p -> next;//temp儲存下一個結點
            p -> next = newh;
            newh = p;
            p = tmp;
        }
        return newh;
    }
};
           

• 這是我一開始寫得，留着對比用，襯托，哈哈哈

思路一樣，但是感覺沒第一個寫得簡潔，但是我的絕對最好了解哈

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL)
            return pHead;      
        ListNode *res,*cur,*next;
        res = new ListNode(-);
        cur = pHead;
        next = cur->next;
        while(cur != NULL)
            {       
            ListNode *first = res->next;
            cur->next = first;
            res->next = cur;

            cur = next;
            next = next->next;       
        }   
        return res->next;  
    }
};
           

方法二

思路：每次都将原第一個結點之後的那個結點放在新的表頭後面。

比如1,2,3,4,5

第一次：把第一個結點1後邊的結點2放到新表頭後面，變成2,1,3,4,5

第二次：把第一個結點1後邊的結點3放到新表頭後面，變成3,2,1,4,5

……

直到： 第一個結點1，後邊沒有結點為止。

代碼如下：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL)
            return pHead;

        ListNode *res,*first,*temp;
        res = new ListNode(-);
        res->next = pHead;

        first = res->next;       //first 始終為第一個結點，不斷後移
        while(first->next!=NULL) //temp為待前差的
            {
            temp = first->next;
            first->next = temp->next;
            temp->next = res->next;
            res->next = temp;          
        }

        return res->next;
    }
};
           

方法三

第三種方法跟第二種方法差不多，第二種方法是将後面的結點向前移動到頭結點的後面，第三種方法是将前面的結點移動到原來的最後一個結點的後面，思路跟第二種方法差不多，就不貼代碼了。

還想整理一些寫得好的，歡迎留言補充

未完待續。。。。。。。。。。。。。。。。。。。