題目：反轉鏈表
定義一個函式，輸入一個鏈表的頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點，
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
題解：
題目不難，定義三個變數pre、cur、next，分別記錄上一個結點，當前結點、下一個結點，通過迭代，依次反轉結點指向，代碼如下：
/**
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null,cur =head ,next = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur =next;
}
return pre;
}
}
當然，本題除了使用迭代方式外，還可以使用遞回的方式解答，
最初我是通過遞回直到找到鏈表的倒數第二個結點，然后將下一個結點的的下一個結點指向本結點，并將尾結點作為首結點遞回回傳，代碼如下：
public ListNode reverseList(ListNode head) {
if(head == null ||head.next == null){
return head;
}
ListNode h =null;
//使用方法遞回，直到鏈表的倒數第二個結點
if(head.next.next!=null){
h = reverseList(head.next);
}
//將結點的下個結點指向本結點
ListNode node = head.next;
node.next = head;
head.next = null;
/*
如果h為空，說明沒有執行方法遞回，即h的下個結點為尾結點，
則將尾結點作為首結點回傳
*/
if(h == null){
return node;
}
//否則則直接回傳h結點，即反轉后的首結點
return h;
}
上面的代碼寫的有些繁瑣，還可以進行適當優化，通過方法遞回，如果當前結點或者下一個結點為null時，直接回傳當前結點作為首結點，否則將下一個結點的下一個結點指向當前結點，并將當前結點的下一個結點置空，實作鏈表的反轉，
public ListNode reverseList(ListNode head) {
if(head == null ||head.next == null){
return head;
}
ListNode h = reverseList(head.next);
head.next.next = head;
head.next = null;
return h;
}
最后，能使用遞回解決的問題，一定可以通過迭代解決，并且方法的遞回對記憶體的開銷較大，
原文鏈接：http://www.daydream.icu/article/detail/1026
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/219869.html
標籤：其他