題目描述

輸入一個(gè)鏈表涩咖，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭繁莹。

解題思路

設(shè)置三個(gè)指針檩互，head為當(dāng)前節(jié)點(diǎn)，pre為當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)咨演，next為當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)闸昨，需要pre和next的目的是讓當(dāng)前節(jié)點(diǎn)從pre->head->next1->next2變成pre<-head next1->next2的過程中，用pre讓節(jié)點(diǎn)反轉(zhuǎn)所指方向薄风，next節(jié)點(diǎn)保存next1節(jié)點(diǎn)防止鏈表斷開

需要注意的點(diǎn)：
1饵较、如果輸入的頭結(jié)點(diǎn)是null，則返回null
2遭赂、鏈表斷裂的考慮

自畫圖解

反轉(zhuǎn)鏈表圖解

參考代碼（Java）

• 結(jié)構(gòu)定義

  public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
      this.val = val;
    }
  }

• 代碼

public class Demo02 {
  public static ListNode ReverseList(ListNode head) {
    if (head == null)
        return null;
    // head為當(dāng)前節(jié)點(diǎn)循诉，如果當(dāng)前節(jié)點(diǎn)為空的話，那就什么也不做撇他，直接返回null茄猫；
    ListNode pre = null;
    ListNode next = null;
    // 當(dāng)前節(jié)點(diǎn)是head，pre為當(dāng)前節(jié)點(diǎn)的前一節(jié)點(diǎn)困肩，next為當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)
    // 需要pre和next的目的是讓當(dāng)前節(jié)點(diǎn)從pre->head->next1->next2變成pre<-head next1->next2
    // 即pre讓節(jié)點(diǎn)可以反轉(zhuǎn)所指方向划纽，但反轉(zhuǎn)之后如果不用next節(jié)點(diǎn)保存next1節(jié)點(diǎn)的話，此單鏈表就此斷開了
    // 所以需要用到pre和next兩個(gè)節(jié)點(diǎn)
    // 1->2->3->4->5
    // 1<-2<-3 4->5
    while (head != null) {
        // 做循環(huán)锌畸，如果當(dāng)前節(jié)點(diǎn)不為空的話勇劣，始終執(zhí)行此循環(huán)，此循環(huán)的目的就是讓當(dāng)前節(jié)點(diǎn)從指向next到指向pre
        // 如此就可以做到反轉(zhuǎn)鏈表的效果
        // 先用next保存head的下一個(gè)節(jié)點(diǎn)的信息蹋绽，保證單鏈表不會(huì)因?yàn)槭ead節(jié)點(diǎn)的原next節(jié)點(diǎn)而就此斷裂
        next = head.next;
        // 保存完next芭毙，就可以讓head從指向next變成指向pre了筋蓖，代碼如下
        head.next = pre;
        // head指向pre后，就繼續(xù)依次反轉(zhuǎn)下一個(gè)節(jié)點(diǎn)
        // 讓pre退敦，head粘咖，next依次向后移動(dòng)一個(gè)節(jié)點(diǎn)，繼續(xù)下一次的指針反轉(zhuǎn)
        pre = head;
        head = next;
    }
    // 如果head為null的時(shí)候侈百，pre就為最后一個(gè)節(jié)點(diǎn)了瓮下，但是鏈表已經(jīng)反轉(zhuǎn)完畢，pre就是反轉(zhuǎn)后鏈表的第一個(gè)節(jié)點(diǎn)
    // 直接輸出pre就是我們想要得到的反轉(zhuǎn)后的鏈表
    return pre;
  }
}

• 測試主方法

public static void main(String[] args) {
  ListNode listNode = new ListNode(1);
  ListNode listNode2 = new ListNode(2);
  ListNode listNode3 = new ListNode(3);
  ListNode listNode4 = new ListNode(4);
  listNode3.next = listNode4;
  listNode2.next = listNode3;
  listNode.next = listNode2;

  ListNode reverseList = ReverseList(listNode);

  while (reverseList != null) {
        System.out.println(reverseList.val);
        reverseList = reverseList.next;
  }
}

• 輸出

4
3
2
1