題目:輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

思路一：利用棧的后進(jìn)先出

創(chuàng)新互聯(lián)主要從事成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)松滋,十載網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

代碼：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
        //利用棧的后進(jìn)先出的特點(diǎn)，最后進(jìn)的最先出
		stack<int> s1;
        ListNode *p=pHead;
        //將鏈表中的每個(gè)元素的值進(jìn)行壓棧
        while(p!=NULL)
        {
            s1.push(p->val);
            p=p->next;
        }
        //出棧，并且將棧頂元素放入鏈表中
        p=pHead;
        while(!s1.empty())
        {
            p->val=s1.top();
            s1.pop();
            p=p->next;
        }
        return pHead;
    }
};

思路二：進(jìn)行摘結(jié)點(diǎn)，然后頭插

代碼：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
        if(pHead==NULL)
        {
            return NULL;
        }
	ListNode *newHead=NULL;
        ListNode *cur=pHead;
        ListNode *tmp=NULL;
        while(cur!=NULL)
        {
            tmp=cur;
            //關(guān)鍵點(diǎn)：一定要讓cur先往后走,再進(jìn)行插入操作
            //不然會(huì)讓原鏈表找不到后面的結(jié)點(diǎn)，結(jié)果就會(huì)變成只有一個(gè)結(jié)點(diǎn)
            cur=cur->next;
            tmp->next=newHead;
            newHead=tmp;
        }
        return newHead;
    }
};

思路三：利用遞歸，找到最后一個(gè)結(jié)點(diǎn)作為函數(shù)的返回值，然后在改變?cè)撴湵淼拿恳粋€(gè)當(dāng)前pHead的位置

代碼：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
		//終止條件
        if(pHead==NULL||pHead->next==NULL)
        {
            return pHead;
        }
        //newHead得到對(duì)應(yīng)的返回值，尾節(jié)點(diǎn)
        ListNode *newHead=ReverseList(pHead->next);
        //然后將當(dāng)先棧幀中的pHead的next進(jìn)行更改
        //比如說1->2->3->4->NULL
        //newHead->4
        //pHead->3
        //4->3->null
        //此時(shí)指向3的還有1->2->3->null
		pHead->next->next=pHead;
        pHead->next=NULL;
        return newHead;
        
    }
};

本文名稱：劍指offer之面試題16：反轉(zhuǎn)鏈表
文章分享：http://sd-ha.com/article24/ieccce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、定制網(wǎng)站、Google、網(wǎng)站改版、移動(dòng)網(wǎng)站建設(shè)、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)