LeetCode 206. 反轉連結清單 - 疊代和遞歸（超詳細解題思路）

1、題目連結

https://leetcode-cn.com/problems/reverse-linked-list/

2、分析

（1）疊代

使用雙指針

直接上代碼

/**
 * 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 cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode p = cur.next;
            cur.next = pre;
            pre = cur;
            //p  = p.next;
            cur = p;
        }
        
        return pre;
    }
}
           

（2）遞歸

遞歸的思路比較難想，見圖

上代碼：

/**
 * 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 cur = head;
        ListNode next = cur.next;
        ListNode newHead = reverseList(next); //遞歸，傳回反轉後的連結清單的新的頭結點
        next.next = cur;
        cur.next = null;
        
        return newHead;
    }
}