反轉一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉鏈表师痕。你能否用兩種方法解決這道題溃睹？
1. 迭代方式
思路：
可以做到in-place的反轉。鏈表反轉后胰坟，實際上只是中間節(jié)點的指針反轉因篇，并且反轉后原來鏈表的頭結點的下一個節(jié)點應該為NULL，而反轉后鏈表的頭結點為原來鏈表的尾節(jié)點。我們可以從頭結點開始惜犀，每次處理兩個節(jié)點之間的一個指針铛碑，將其反轉過來狠裹。然后再處理接下來兩個節(jié)點之間的指針……直至遇到尾節(jié)點虽界，設置為新鏈表的頭結點即可。
實現：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode rHead = null; // 反轉后的頭節(jié)點
ListNode curr = head; // 當前處理節(jié)點
ListNode pTail = null; // 反轉后尾節(jié)點
while (curr != null) {
ListNode tmp = curr.next;
if (tmp == null) {
rHead = curr;
}
curr.next = pTail;
pTail = curr;
curr = tmp;
}
return rHead;
}
}
2. 遞歸方式：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode rHead = reverseList(head.next); // 反轉得到新鏈表的頭節(jié)點
head.next.next = head; // 當前節(jié)點的下一個節(jié)點的next指針反轉過來
head.next = null; // 設置新鏈表的尾節(jié)點
return rHead;
}
}
