定義一個函數(shù)，輸入一個鏈表的頭節(jié)點(diǎn)讹挎，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)校赤。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
限制：
0 <= 節(jié)點(diǎn)個數(shù) <= 5000
注意：本題與主站 206 題相同：https://leetcode-cn.com/problems/reverse-linked-list/
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
解題思路
這道題題面是相當(dāng)?shù)暮唵危a量也是很小淤袜，但確實(shí)要弄明白怎么反轉(zhuǎn)痒谴，說白就是控制指針，做之前在紙上把圖畫明白對解題很有幫助铡羡。
我提交了兩種解法积蔚，思路稍有不同，但基本思路是一致的就是把當(dāng)前指針的next指向前一個節(jié)點(diǎn)烦周，為了保證鏈條不斷掉尽爆，記得要保存正序下當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)。
正序.png
- 生成一個為null 的Pre 前置節(jié)點(diǎn)读慎，將頭節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn) Cur
- 首先保存當(dāng)前節(jié)點(diǎn)Cur的下一個節(jié)點(diǎn)為 Next
- 將當(dāng)前節(jié)點(diǎn)的next指向前一個節(jié)點(diǎn) Pre漱贱，即當(dāng)前節(jié)點(diǎn)反轉(zhuǎn)
- 調(diào)整指針，使前置節(jié)點(diǎn)Pre變成反轉(zhuǎn)后的最新節(jié)點(diǎn)夭委，當(dāng)前節(jié)點(diǎn)指向原來的下一個節(jié)點(diǎn)幅狮。
直至所有節(jié)點(diǎn)反轉(zhuǎn)完成。
反轉(zhuǎn)過程.png
/**
* 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 Pre = null;
ListNode Cur = head;
while(Cur != null){
//保存當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
ListNode Next = Cur.next;
//反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)
Cur.next = Pre;
// 調(diào)整指針
Pre = Cur;
Cur = Next;
}
return Pre;
}
}
