單鏈表反轉(zhuǎn)

參考：https://blog.csdn.net/superxiaolong123/article/details/86687733

首先要了解一個(gè)鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：

在這里插入圖片描述

value代表該節(jié)點(diǎn)存儲(chǔ)的值，next指向下一個(gè)節(jié)點(diǎn)浦旱，next可能指向一個(gè)單一節(jié)點(diǎn)杉适，也可能指向一個(gè)鏈表蝴蜓，也可能指向null(代表尾節(jié)點(diǎn))。

方法一：頭節(jié)點(diǎn)插入法(推薦)
實(shí)現(xiàn)步驟：

創(chuàng)建一個(gè)帶頭節(jié)點(diǎn)的鏈表resultList
定義一個(gè)循環(huán)鏈表變量p，p的初始值為待反轉(zhuǎn)的鏈表
遍歷待反轉(zhuǎn)的鏈表挡闰，遍歷條件為 (p !=null)
3.1 定義一個(gè)臨時(shí)鏈表變量tempList保存p->next的值（因?yàn)閜->next值會(huì)改變）头岔，用于下一次循環(huán)。
3.2 把p當(dāng)前指向的首節(jié)點(diǎn)和resultList鏈表的頭節(jié)點(diǎn)之后的節(jié)點(diǎn)拼接起來劲赠。（resultlist.next其實(shí)=null,相當(dāng)于把插入節(jié)點(diǎn)的next置為null涛目，等價(jià)于p.next = null）
3.3 把3.2步驟中拼接的節(jié)點(diǎn) 再拼接到resultList頭節(jié)點(diǎn)后。
3.4 p重新賦值為3.1步驟中保存的tempList的值凛澎。
返回resultList->next.即反轉(zhuǎn)后的鏈表泌绣。

圖解：

在這里插入圖片描述

圖1就是待反轉(zhuǎn)的原始鏈表，圖2是帶頭節(jié)點(diǎn)的鏈表resultList预厌。
可以看到p是一個(gè)循環(huán)變量阿迈，初始值指向待反轉(zhuǎn)的原始鏈表。
通過p變量遍歷鏈表轧叽，在遍歷中（列舉的值為第一次循環(huán)的情況）：

定義一個(gè)臨時(shí)鏈表變量tempList保存p->next的值苗沧，tempList指向圖1.2
把p當(dāng)前指向的首節(jié)點(diǎn)(圖1.1)和resultList鏈表的頭節(jié)點(diǎn)之后的節(jié)點(diǎn)（圖2.2）拼接起來。
把3.2步驟中拼接的節(jié)點(diǎn)(圖3.2) 再拼接到resultList頭節(jié)點(diǎn)后炭晒。
p重新賦值為3.1步驟中保存的tempList的值待逞，即圖1.2。

最后返回resultList->next网严，也就是去除了頭節(jié)點(diǎn)-1的值识樱。

通過頭結(jié)點(diǎn)插入法實(shí)現(xiàn)鏈表反轉(zhuǎn)功能，主要難點(diǎn)就是在循環(huán)中的3.2和3.3步驟的理解。
需要注意的是怜庸，就是關(guān)注循環(huán)變量p的值当犯，也就是指向的變化，傳統(tǒng)的遍歷過程就是條件為p!=null,處理,p=p->next割疾。但是在這個(gè)頭結(jié)點(diǎn)插入代碼中嚎卫，p->next的值發(fā)生的變化，因?yàn)橐獙esultList結(jié)果鏈表的內(nèi)容拼接到p的首節(jié)點(diǎn)后宏榕，所以要定義一個(gè)臨時(shí)變量存p->next拓诸。

    public static ListNode reverseListByInsert(ListNode listNode){
        //定義一個(gè)帶頭節(jié)點(diǎn)的
        ListNode resultList = new ListNode(-1);
        //循環(huán)節(jié)點(diǎn)
        ListNode p = listNode;
        while(p!= null){
            //保存插入點(diǎn)之后的數(shù)據(jù)
            ListNode tempList = p.next;
            p.next = resultList.next;//連接頭節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)（參照頭插法圖）
            resultList.next = p;
            p = tempList;
        }
        return resultList.next;
    }

邏輯參考2

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

ListNode* reverseList(ListNode* head) {
    ListNode *phead=new ListNode(-1);//注意第6行l(wèi)istNode(int x)中括號(hào)要寫值，這里隨便寫麻昼，因?yàn)轭^節(jié)點(diǎn)的val不重要
    phead->next=NULL;//申請一個(gè)頭節(jié)點(diǎn)奠支，在空結(jié)點(diǎn)后插入值
    ListNode *ptemp;//臨時(shí)結(jié)點(diǎn)，存放插入的值
    ListNode *t;//控制插入節(jié)點(diǎn)的值
    t=head;//從第一個(gè)結(jié)點(diǎn)開始
    while(t!=NULL){
    ptemp=t;
    t=t->next;
    ptemp->next=phead->next;//phead->next第一次其實(shí)=null
    phead->next=ptemp;
    }
    return phead->next;
  }

方法二：就地反轉(zhuǎn)1
頭結(jié)點(diǎn)插入法的實(shí)質(zhì)是重新創(chuàng)建了一個(gè)新的鏈表抚芦，通過遍歷待反轉(zhuǎn)鏈表胚宦，將鏈表每一個(gè)節(jié)點(diǎn)插入到創(chuàng)建的鏈表中，然后的到的這個(gè)創(chuàng)建的鏈表就是反轉(zhuǎn)后的鏈表燕垃。而就地反轉(zhuǎn)實(shí)質(zhì)就是在待反轉(zhuǎn)鏈表基礎(chǔ)上修改節(jié)點(diǎn)順序得到反轉(zhuǎn)鏈表枢劝。所以原理還是不同的。

圖解：

在這里插入圖片描述

個(gè)人認(rèn)為就地反轉(zhuǎn)比頭結(jié)點(diǎn)插入稍微難理解一點(diǎn)卜壕。
宏觀上來看您旁，要實(shí)現(xiàn)節(jié)點(diǎn)1和節(jié)點(diǎn)2反轉(zhuǎn)，需要將節(jié)點(diǎn)1插入節(jié)點(diǎn)2和節(jié)點(diǎn)3當(dāng)中轴捎，然后將頭節(jié)點(diǎn)為2的鏈表插入結(jié)果鏈表頭結(jié)點(diǎn)后面鹤盒，然后再后移一個(gè)節(jié)點(diǎn)做同樣的操作。
然而涉及到兩個(gè)節(jié)點(diǎn)的循環(huán)賦值侦副，這個(gè)操作順序就比較重要了侦锯。
正確的步驟是先將節(jié)點(diǎn)2切分出來，再將節(jié)點(diǎn)2插入-1和1之間秦驯。

實(shí)現(xiàn)步驟

創(chuàng)建一個(gè)帶頭節(jié)點(diǎn)的鏈表resultList尺碰，頭結(jié)點(diǎn)指向待反轉(zhuǎn)的鏈表。
創(chuàng)建p译隘、pNext兩個(gè)用于循環(huán)操作亲桥，分別指向兩個(gè)待反轉(zhuǎn)節(jié)點(diǎn)的位置,初始值如圖所示，指向1和2
遍歷帶反轉(zhuǎn)的鏈表固耘，循環(huán)條件是pNext!=null.
3.1 從鏈表中分割出pNext節(jié)點(diǎn)题篷，也就是讓p指向pNext->next。
3.2 讓pNext指向經(jīng)過3.1操作之后的resultList.next（1->3->4->5）
3.3 讓resultList頭結(jié)點(diǎn)指向pNext(2->1->3->4->5)
3.4 讓pNext指向p的下一個(gè)節(jié)點(diǎn)
難點(diǎn)在于理解循環(huán)中resultList.next指向性的變化厅目，以及p和pNext兩個(gè)變量的變化番枚，p指向的鏈表首結(jié)點(diǎn)永遠(yuǎn)是1,只是節(jié)點(diǎn)1在resultList鏈表中位置在發(fā)生變化法严，而pNext是隨著p移動(dòng)的，腦子中間可以有一個(gè)擺繩模型葫笼，在起始點(diǎn)位置發(fā)力深啤，繩子的高點(diǎn)位置會(huì)移到繩尾，那個(gè)最高點(diǎn)就是p變量位置渔欢。

public static ListNode reverseListByLocal(ListNode listNode){
        ListNode resultList = new ListNode(-1);
        resultList.next= listNode;
        ListNode p = listNode;
        ListNode pNext = p.next;
        while (pNext!=null){
            p.next = pNext.next;
            pNext.next = resultList.next;
            resultList.next = pNext;
            pNext=p.next;
        }
        return resultList.next;
    }

頭插法分析圖：

image.png

方法二：就地反轉(zhuǎn)2(`推薦`)

參考：https://www.cnblogs.com/byrhuangqiang/p/4311336.html

2.1 思路

把當(dāng)前鏈表的下一個(gè)節(jié)點(diǎn)pCur插入到頭結(jié)點(diǎn)dummy的下一個(gè)節(jié)點(diǎn)中，就地反轉(zhuǎn)瘟忱。

dummy->1->2->3->4->5的就地反轉(zhuǎn)過程：
dummy->2->1->3->4->5
dummy->3->2->1->4->5
dummy->4>-3->2->1->5
dummy->5->4->3->2->1

2.2 解釋

1初始狀態(tài)

image

2 過程

pCur是需要反轉(zhuǎn)的節(jié)點(diǎn)奥额。

prev連接下一次需要反轉(zhuǎn)的節(jié)點(diǎn)
反轉(zhuǎn)節(jié)點(diǎn)pCur
糾正頭結(jié)點(diǎn)dummy的指向
pCur指向下一次要反轉(zhuǎn)的節(jié)點(diǎn)

偽代碼

1 prev.next = pCur.next;
2 pCur.next = dummy.next;
3 dummy.next = pCur;
4 pCur = prev.next;

image

3 循環(huán)條件

pCur is not null

2.3 代碼

// 1.就地反轉(zhuǎn)法
    public ListNode reverseList1(ListNode head) {
        if (head == null)
            return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev =head;//修改了原文的dummy.next 
        ListNode pCur = prev.next;
        while (pCur != null) {
            prev.next = pCur.next;
            pCur.next = dummy.next;
            dummy.next = pCur;
            pCur = prev.next;
        }
        return dummy.next;
    }

2.4 總結(jié)

1個(gè)頭結(jié)點(diǎn)，2個(gè)指針访诱，4行代碼
注意初始狀態(tài)和結(jié)束狀態(tài)垫挨，體會(huì)中間的圖解過程。

單鏈表反轉(zhuǎn)

頭插法分析圖：

方法二：就地反轉(zhuǎn)2(推薦)

2.1 思路

2.2 解釋

1初始狀態(tài)

2 過程

3 循環(huán)條件

2.3 代碼

2.4 總結(jié)

方法二：就地反轉(zhuǎn)2(`推薦`)