反轉鏈表
- 問題
- 思路
- 代碼
- 迭代
- 遞回
問題
給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，
如 1->3->5->7->9,翻轉之后:9->7->5->3->1
思路
因為不是陣列結構，不能使用雙指標，從兩頭向中遍歷翻轉(error)；
所以我們只能通過改變next域的方向來翻轉，
代碼
解釋都在注釋中，
迭代
public ListNode reverseList(ListNode head) {
//為鏈表空，直接回傳
if(head==null){
return null;
}
//cur當前 pre 前驅
//curNext 記錄cur.next翻轉前的參考，
//如果不記錄那么翻轉一次就找不到下一個位置了
ListNode cur=head;
ListNode pre=null;
ListNode curNext=null;
//如果這里想不通，畫一下圖，對著代碼來就ok了
while(cur!=null){
curNext=cur.next;
cur.next=pre;
pre=cur;
cur=curNext;
}
return pre;
}
遞回
遞回等展開到最后，從后向前的翻轉，可以多去理解上面的圖片，
public ListNode reverseList(ListNode head) {
//當head為空,或者head的next為空,那么就可以歸了
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
//這里也就可以理解為，把head的next域指向的結點，
//讓其結點指回來，等于在翻轉
head.next.next = head; //cur=head.next;cur.next=head;
head.next = null;//這步是為了把翻轉后的最后一個結點(未翻轉前的第一個結點)指向null,不然第一個結點和第二個結點互相指向了
return newHead; //這里便一直是新的頭結點(9)
}
}
使用哪種方法還是得看長度，如果鏈表很長，使用遞回容易出現StackOverflowError(堆疊溢位錯誤)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294944.html
標籤：其他