<abbr id="2oi2q"></abbr>

劍指offer：反轉鏈表（Java）

stonezhu 發布于2019-08-16 18:39 / 1993人閱讀

摘要：問題描述輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。通過循環遍歷當前鏈表，在遍歷過程中反轉鏈表，當前節點遍歷到最后為時，循環停止，此時當前節點為，所以它的前一個節點就是新鏈表的第一個節點。

1.問題描述

輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。

2.思路

首先要判斷給出的頭節點是否為空，如果為空直接返回，如果不為空才可以進行反轉。
因為每個節點只有一個next指針記錄它的下一個節點的地址，所以應該需要兩個變量分別記錄當前節點左右兩邊的節點，否則反轉鏈表之后就沒辦法連上后面的節點了。
通過循環遍歷當前鏈表，在遍歷過程中反轉鏈表，當前節點遍歷到最后為null時，循環停止，此時當前節點為null，所以它的前一個節點就是新鏈表的第一個節點。
注意：當前節點的前一個節點是從null開始的，當前節點一定要放在中間，記錄它的前后各一個節點，否則循環過程易錯。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null)
            return head;    //head為null直接返回。
        ListNode pNode = head;    //表示當前節點
        ListNode pre = null;    //當前節點的前一個節點
        ListNode next = null;    //當前節點的后一個節點
        while(pNode != null){
            next = pNode.next;    //記錄下當前節點的下一個節點
            pNode.next = pre; //反轉鏈表
            pre = pNode;    //讓prej和pNode都向后移動一位，next不用變了，因為上面會自動根據pNode獲取next節點。
            pNode = next;
        }
        return pre;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75507.html

劍指offer系列——劍指 Offer 24. 反轉鏈表（C語言）

摘要：假設反轉對象節點為，反轉指向的結點為，反轉后指向的結點為首結點。當然也可以根據棧先進后出的特點，使用棧反轉鏈表。 ??前面的話?? 大家好！博主開辟了一個新的專欄—...

weakish 2021-09-03 10:29 評論0 收藏0
劍指offer系列——劍指 Offer 06. 從尾到頭打印鏈表（C語言）

摘要：導航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結劍指從尾到頭打印鏈表題目詳情輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值用數組返回。時間復雜度方法先反轉鏈表并求長度，在將反轉后的鏈表數據拷貝至數組中。 ...

DevTTL 2021-09-04 16:41 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
劍指offer:合并兩個排序的鏈表（Java）

摘要：問題描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。 1.問題描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。 2.思路方法1:非遞歸方法根據題目這個很類似排序中的外排過程,兩個數組分別排好序,然后再把他們整體進行排序.所以這道題思想很簡單,就是用兩個變量分別遍歷兩個鏈表.比較遍歷到...

darkbaby123 2019-08-16 18:39 評論0 收藏0