LeetCode鏈接：https://leetcode.cn/problems/reverse-linked-list/

題目：給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

示例1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例2：

輸入：head = [1,2]
輸出：[2,1]

相信很多人第一次拿到這種題目跟我一樣，想的就是再建立一個空間，但是這樣太浪費記憶體了，有更好的辦法解決，

思路

其實只需要改變鏈表的next指標的指向，直接將鏈表反轉，而不用重新定義一個新的鏈表，如圖所示（來自代碼隨想錄）:

206_反轉鏈表

之前鏈表的頭節點是元素1，反轉之后頭結點就是元素5 ，這里并沒有添加或者洗掉節點，僅僅是改變next指標的方向，

那么接下來看一看是如何反轉的呢？

首先定義一個cur指標，指向頭結點，再定義一個pre指標，初始化為null，然后就要開始反轉了，首先要把 cur->next 節點用tmp指標保存一下，也就是保存一下這個節點，為什么要保存一下這個節點呢，因為接下來要改變 cur->next 的指向了，將cur->next 指向pre ，此時已經反轉了第一個節點了，

接下來，就是回圈走如下代碼邏輯了，繼續移動pre和cur指標，最后，cur 指標已經指向了null，回圈結束，鏈表也反轉完畢了，此時我們return pre指標就可以了，pre指標就指向了新的頭結點，

java代碼如下：

// 雙指標
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一個節點
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

還有一種遞回的方法如下：

// 遞回 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一個節點
        cur.next = prev;// 反轉
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

這又是一道雙指標的題，不難，只要把之前題弄懂即可！！！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539035.html

標籤：其他

上一篇：opencv的學習記錄(python)

下一篇：力扣09 判斷一個數是否是回文數

反轉鏈表-LeetCode206 改變指向

思路