反轉(zhuǎn)一個單鏈表。如下示例:：
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

public class ListNode {int val;ListNode next;ListNode(int x) {val = x;} }

一、 迭代法：

注意觀察示例：1->2->3->4->5->NULL的反轉(zhuǎn)可以看成：NULL<-1<-2<-3<-4<-5。

會發(fā)現(xiàn)鏈表的反轉(zhuǎn)基本上就是箭頭的方向的反轉(zhuǎn)，即節(jié)點前驅(qū)和后繼互換角色。

我們定義三個變量cur，pre和next分別表示當前節(jié)點，以及其前驅(qū)后繼。cur初始化為head，其他初始化為NULL。

我們從頭節(jié)點1開始遍歷，1的next和pre原來分別是2和NULL(初始值)互換后1的next和pre變成NULL和2，依次這樣遍歷下去。

注意最后應該返回pre，不是cur。遍歷結(jié)束后cur的值是NULL。
代碼如下：

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;}

?

方法2:頭插法

反轉(zhuǎn)從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉(zhuǎn)。

說明:
1 ≤?m?≤?n?≤ 鏈表長度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

//頭插法 每次把cur.next那個節(jié)點放在頭部//m = 1, n = length的時候全部反轉(zhuǎn)(直到cur.next為空)public ListNode reverseBetween(ListNode head, int m, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;for(int i = 1;i<m;i++) pre = pre.next;//pre是要反轉(zhuǎn)部分的先序節(jié)點,相當于dummyListNode cur = pre.next;for(int i = m;i<n;i++){ListNode nxt = cur.next;cur.next = cur.next.next;//pre.next = nxt;//nxt.next = cur; cur始終沒變，這樣寫不行 會造成節(jié)點丟失nxt.next = pre.next;pre.next = nxt;}return dummy.next;}

二、遞歸法：
遞歸法和迭代法思路是一樣的。
代碼如下：
?

public ListNode reverseList(ListNode head){if(head == null || head.next == null){return head;}ListNode n = reverseList(head.next);head.next.next = head;//head.next是反轉(zhuǎn)鏈表的末尾head.next = null;return n;}

只是注意兩個地方：
如果head是空或者遍歷到最后節(jié)點的時候，應該返回head。
代碼5，6行。節(jié)點替換的時候不要用n來代替head->next；因為對于遞歸來說它們不是等價的。但是head->next->next 等價于 n->next。

總結(jié)

以上是生活随笔為你收集整理的反转链表--清晰易懂的两种方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。