@1：反轉(zhuǎn)一個單鏈表： https://leetcode-cn.com/problems/reverse-linked-list/

題目描述：
反轉(zhuǎn)一個單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

#解法參考1#
#解法參考2#

解法1：迭代法（ 記錄 》反轉(zhuǎn) 》后移 》后移 ）

記錄now.next，反轉(zhuǎn)now.next逛薇，
后移prev肮蛹，后移now胖烛；

• now 代表當(dāng)前節(jié)點孤个；
• 原前驅(qū)陋率、原后繼驮宴、原方向的“原”逮刨，指“反轉(zhuǎn)前”；
• 線性記錄特性 　“精兵未動堵泽，糧草先行” ：
  如下思路的1修己、 3兩步，
  都是為了2迎罗、 4兩步執(zhí)行之后睬愤，有用信息不丟失；
  .
  想要改變now的后繼纹安，先用next將now原后繼記錄下來尤辱；
  想要改變now砂豌，先用prev記錄下來；
  
  
  

代碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode now = head;
    while (now != null) {
      ListNode next = now.next;    //next 指向now.next
      now.next = prev;      //now.next 指向prev
      prev = now;
      now = next;
    }

    return prev;
    }
}

解法思路如下：

• 首先光督，ListNode head把源節(jié)點的頭結(jié)點傳進(jìn)來阳距；
• 循環(huán)中四行代碼，每一行的右邊都是下一行的左邊结借，
  即改動前先存儲（謀定而后動筐摘，重要思想！Ｓ掣Ｐ罴稹！）努隙，
  環(huán)環(huán)相扣球恤，安全可靠；

1. 記錄now原后繼now.next（因為下一步now.next就要改指向?qū)崿F(xiàn)反轉(zhuǎn)了）：
   先將　當(dāng)前節(jié)點now反轉(zhuǎn)前的下一個節(jié)點now.next　紀(jì)錄下來荸镊，即ListNode next = now.next;
   記錄下來的原因是最后第四行要用咽斧，
   讓本輪的now結(jié)點能往后移動；

2. now后繼指向原前驅(qū)（核心：方向反轉(zhuǎn)）：
   然后讓當(dāng)前節(jié)點反轉(zhuǎn)前的下一個節(jié)點的 “指針”now.next置為反轉(zhuǎn)前的上一節(jié)點prev躬存，即now.next = prev;

3. 原前驅(qū)后移（基于原方向）：
   再將當(dāng)前節(jié)點紀(jì)錄下來,即原前驅(qū)后移张惹，prev = now;

4. now后移：
   再讓反轉(zhuǎn)前當(dāng)前節(jié)點的下一節(jié)點next變?yōu)楫?dāng)前節(jié)點now;即now = next;

now != null即next不為空，表示鏈表還有節(jié)點未處理岭洲，
   最后now == null宛逗，即鏈表已盡，
   此時盾剩，next = now = 表尾往后一個“節(jié)點”（null）雷激，
   prev指向反轉(zhuǎn)前最后一個節(jié)點，
   也即反轉(zhuǎn)后第一個節(jié)點;
   跳出while循環(huán)告私，
   所以最后return prev;

解法2：遞歸

思路如下：
0.利用遞歸首先找到單鏈表的最后一個節(jié)點屎暇；

最后一個節(jié)點存儲在re里面，
re在找到最后一個節(jié)點時被賦值且其永遠(yuǎn)為最后一個節(jié)點的值,保持不變驻粟；

從找到最后一個節(jié)點開始根悼，
從最后往前的方向，每一層遞歸反轉(zhuǎn)一對節(jié)點 / 一個指向;

1. if 判斷蜀撑，判斷是否是空鏈表（head == null ||）或者是否是鏈表的最后一個節(jié)點（遞歸終止條件）挤巡；
2. 配置好next；next = head.next屯掖；
3. 剪短原方向：head.next = null;
4. 把next丟進(jìn)遞歸玄柏；
   找到最后一個節(jié)點的時候會return回來；
5. 反轉(zhuǎn)一對節(jié)點 / 一個方向：next.next = head;
   6.返回

核心同樣是四行代碼贴铜，（可以結(jié)合運(yùn)行草圖理解）
前兩行不斷剪除原來的指向
ListNode next = head.next;　　//next 指向head.next
head.next = null;　　//剪除原來的指向
ListNode re = reverseList(next);　　//遞歸找到末節(jié)點粪摘，記錄下來付給re
next.next = head;　　//反轉(zhuǎn)指向

代碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    if(head == null || head.next==null)return head;
    ListNode next = head.next;
    head.next = null;
    ListNode re = reverseList(next);
    next.next = head;
    return re;
    }
}

注意：
要if判斷中要加上head == null ||瀑晒，防止輸出空鏈表的情況；
否則會報空指針的錯：java.lang.NullPointerException

@2：兩兩交換鏈表中的節(jié)點：https://leetcode-cn.com/problems/swap-nodes-in-pairs/

@3：判斷鏈表是否有環(huán)：https://leetcode-cn.com/problems/linked-list-cycle/

1.哈希表
while(head != null)判斷是否為表尾徘意；
nodes.add(head);如果新節(jié)點沒有包含苔悦，吃進(jìn)去，一直吃椎咧；
終焉兩種情況玖详，
2.1. 無環(huán)，直到head == null還沒重復(fù)勤讽，false
2.2. 有環(huán)蟋座，if(nodes.contains(head))直到加到重復(fù)的，true

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodes = new HashSet<>();
        while(head != null){
            if(nodes.contains(head))
                return true;
            else 
                nodes.add(head);

            head = head.next;
        }
        return false;
    }
}

復(fù)雜度分析

時間復(fù)雜度：O(n)O(n)脚牍，對于含有 nn 個元素的鏈表向臀，我們訪問每個元素最多一次。添加一個結(jié)點到哈希表中只需要花費 O(1)O(1) 的時間诸狭。

空間復(fù)雜度：O(n)O(n)券膀，空間取決于添加到哈希表中的元素數(shù)目，最多可以添加 nn 個元素驯遇。

2.雙指針：

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

1. 空鏈表 head == null 芹彬，
   一節(jié)點鏈表 head.next == null ，
   無環(huán)
   if (head == null || head.next == null) {
   return false;
   }

2. 初始化叉庐，快前慢后
   ListNode slow = head;
   ListNode fast = head.next;

3. 沒有追上舒帮，就一直跑
   while (slow != fast)
   ...
   slow = slow.next;
   fast = fast.next.next;

終焉兩種情況：
3.1. 有環(huán)，遲早追上
slow == fast
跳出循環(huán)陡叠，true会前；

3.2. 無環(huán)，快針遲早到鏈尾匾竿，flase
if (fast == null || fast.next == null) {
return false;
}

• fast == null 跑過頭了到尾結(jié)點的next；

• fast.next == null 剛剛好跑到尾結(jié)點

  
  
  
  

  復(fù)雜度分析

時間復(fù)雜度：O(n)O(n)蔚万，讓我們將 nn 設(shè)為鏈表中結(jié)點的總數(shù)岭妖。為了分析時間復(fù)雜度，我們分別考慮下面兩種情況反璃。

鏈表中不存在環(huán)：
快指針將會首先到達(dá)尾部昵慌，其時間取決于列表的長度，也就是 O(n)O(n)淮蜈。

鏈表中存在環(huán)：
我們將慢指針的移動過程劃分為兩個階段：非環(huán)部分與環(huán)形部分：

慢指針在走完非環(huán)部分階段后將進(jìn)入環(huán)形部分：此時斋攀，快指針已經(jīng)進(jìn)入環(huán)中 \text{迭代次數(shù)} = \text{非環(huán)部分長度} = N迭代次數(shù)=非環(huán)部分長度=N

兩個指針都在環(huán)形區(qū)域中：考慮兩個在環(huán)形賽道上的運(yùn)動員 - 快跑者每次移動兩步而慢跑者每次只移動一步。其速度的差值為 1梧田，因此需要經(jīng)過 \dfrac{\text{二者之間距離}}{\text{速度差值}}
速度差值
二者之間距離
?
次循環(huán)后淳蔼，快跑者可以追上慢跑者侧蘸。這個距離幾乎就是 "\text{環(huán)形部分長度 K}環(huán)形部分長度 K" 且速度差值為 1，我們得出這樣的結(jié)論 \text{迭代次數(shù)} = \text{近似于}迭代次數(shù)=近似于 "\text{環(huán)形部分長度 K}環(huán)形部分長度 K".

因此鹉梨，在最糟糕的情形下讳癌，時間復(fù)雜度為 O(N+K)O(N+K)，也就是 O(n)O(n)存皂。

空間復(fù)雜度：O(1)O(1)晌坤，我們只使用了慢指針和快指針兩個結(jié)點，所以空間復(fù)雜度為 O(1)O(1)旦袋。

@4：環(huán)形鏈表：https://leetcode-cn.com/problems/linked-list-cycle-ii/

@5：每 k 個節(jié)點一組翻轉(zhuǎn)鏈表：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/