【問(wèn)題描述】[中等]

定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(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)個(gè)數(shù) <= 5000

【解答思路】

1. 雙指針/頭插法

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public ListNode reverseList(ListNode head) {//申請(qǐng)節(jié)點(diǎn)，pre和 cur，pre指向nullListNode pre = null;ListNode cur = head;ListNode tmp = null;while(cur!=null) {//記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)tmp = cur.next;//然后將當(dāng)前節(jié)點(diǎn)指向precur.next = pre;//pre和cur節(jié)點(diǎn)都前進(jìn)一位pre = cur;cur = tmp;}return pre;} }

2. 遞歸

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public ListNode reverseList(ListNode head) {//遞歸終止條件是當(dāng)前為空，或者下一個(gè)節(jié)點(diǎn)為空if(head==null || head.next==null) {return head;}//這里的cur就是最后一個(gè)節(jié)點(diǎn)ListNode cur = reverseList(head.next);//這里請(qǐng)配合動(dòng)畫(huà)演示理解//如果鏈表是 1->2->3->4->5，那么此時(shí)的cur就是5//而head是4，head的下一個(gè)是5，下下一個(gè)是空//所以head.next.next 就是5->4head.next.next = head;//防止鏈表循環(huán)，需要將head.next設(shè)置為空head.next = null;//每層遞歸函數(shù)都返回cur，也就是最后一個(gè)節(jié)點(diǎn)return cur;} }

【總結(jié)】

1.鏈表題目 遞歸和雙指針?biāo)枷敕浅Ｖ匾?/h6>

2. 鏈表題目一定要畫(huà)圖

轉(zhuǎn)載：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/ru-guo-ni-kan-wan-ping-lun-he-ti-jie-huan-you-wen-/

鏈接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/dong-hua-yan-shi-duo-chong-jie-fa-206-fan-zhuan-li/

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[24]题[反转链表][递归][双指针][头插法]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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