問題描述
反轉一個單鏈表，
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
解題思路(頭插法)：
我們要想實作的反轉并不僅僅是資料的移位，而是涉及到結點的移動，所以我們無法使用陣列，
我們都知道，頭插法得到的鏈表序列與插入的順序剛好相反，因此我們可以采取這樣的辦法來解決這個問題，
頭插法即每次將插入的結點插入到鏈表的第一個位置，比如我們插入1,2,3,4.那么第1次插入1，第二次將2插入到1的前面，第3次將3插入在2的前面，第4次將4插入3的前面，
1.先定義一個節點reverseHead =new HeroNode();
2.從頭到尾遍歷原來的鏈表，每遍歷一一個節點，就將其取出，并放在新的鏈表reverseHead的最前端.
3.原來的鏈表的head.next = reverseHead.next
代碼實作：
本題思路非常簡單，但是實作起來卻處處有坑，博主除錯了很久才成功，
public ListNode reverseList(ListNode head) {
//如果當前鏈表為空，或者只有一個結點，無需反轉，直接回傳
if(head==null || head.next==null){
return head;
}
//定義一個輔助的指標（變數），幫助我們遍歷原來的鏈表
ListNode cur=head;
//這個變數很重要，指向當前結點的下一個結點，否則你移走當前結點的時候，整個鏈表就斷掉了
ListNode next=null;
ListNode reverseHead=new ListNode(-1); //頭結點
reverseHead.next=null;
//遍歷原來的鏈表，每遍歷一個結點，就將其取出，并放在新的鏈表的最前端
while(cur!=null){
//首先要保留cur的下面一個結點，因為后面需要使用
next=cur.next;
cur.next=reverseHead.next; //將cur的下一個結點指向新的鏈表最前端
reverseHead.next=cur;
//這里面只能是cur=next,而不能是cur=cur.next,因為我們已經修改cur.next到新的鏈表中去了
cur=next;
}
return reverseHead.next;
}
總結：
本題關鍵點1：要使用next指標，next指標非常重要，指向當前結點的下一個結點，否則你移走當前結點的時候，整個鏈表就斷掉了，在我們進行遍歷的程序中，我們會讓cur.next指向reverseHead.next，此時cur后面的鏈就都斷開了，所以我們需要在移動cur指標之前，保存好cur.next，
本題關鍵點2：cur后移不再是cur=cur.next,而是cur=next,因為我們已經改動過了cur.next指標了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/258448.html
標籤：其他
上一篇：提交代碼到GitHub