題目描述 牛客網(wǎng)

• 定義一個函數(shù)运怖，輸入一個鏈表的頭結(jié)點灵巧，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點

題目解讀

• 劍指Offer 142
• 思路一搀矫、書上思路，定義兩個三個指針
• 思路二刻肄、遞歸

代碼

• 思路一瓤球、書上思路，定義三個指針

// 第一輪代碼
#include<iostream>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution {
public:

    ListNode* ReverseList(ListNode* pHead) {
        ListNode *zuo = NULL;
        ListNode *zhong = NULL;
        ListNode *you = NULL;

        if(!pHead){
            return NULL;
        }

        zhong = pHead;
        while(zhong){
            you = zhong -> next;
            zhong -> next = zuo;
            zuo = zhong;
            zhong = you;
        }

        return zuo;
    }


    ListNode* create(){
        ListNode *p;
        ListNode *head = NULL;
        ListNode *tail = NULL;

        for(int i=1; i <= 6; i++){
            p = new ListNode(i);

            if(!head){
                head = p;
            }
            else{
                tail -> next = p;
            }
            tail = p;
        }

        return head;
    }

    void print_Node(ListNode *head){
        while(head){
            cout<<head->val<<" ";
            head = head->next;
        }
        cout<<endl;
    }
};

main(){
    Solution ss;
    ListNode *head = NULL;

    head = ss.create();
    ss.print_Node(head);
    head = ss.ReverseList(head);
    ss.print_Node(head);
}

// 思路一敏弃、第二輪代碼
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL){
            return NULL;
        }
        
        ListNode* zuo     = NULL;
        ListNode* current = pHead;
        ListNode* you     = NULL;
        while(current->next != NULL){
            you = current->next;
            current->next = zuo;
            zuo = current;
            current = you;
        }
        current->next = zuo;
        return current;
    }
};

• 思路二卦羡、遞歸

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL || pHead -> next == NULL){
            return pHead;
        }
        else{
            ListNode *newHead = ReverseList(pHead->next);
            pHead -> next -> next = pHead;
            pHead -> next = NULL;
            return newHead;
        }
    }
};

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // 鏈表為空直接返回
        if(pHead == NULL){
            return pHead;
        }
        return core(pHead);
    }
    
    ListNode*　core(ListNode* pHead){
        if(pHead -> next == NULL){
            return pHead;
        }
        else{
            // 一直遞歸到鏈尾
            ListNode *newHead = core(pHead->next);
            pHead -> next -> next = pHead; // 翻轉(zhuǎn)鏈表的指向
            pHead -> next = NULL;    // 賦值為空，防止鏈表錯亂
            return newHead;  // 新鏈表永遠指向的是原鏈表的鏈尾
        }
    }
    
};

總結(jié)展望

• 很值得思考的題目