您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了“LeetCode怎樣反轉(zhuǎn)鏈表”,內(nèi)容簡而易懂,條理清晰,希望能夠幫助大家解決疑惑,下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode怎樣反轉(zhuǎn)鏈表”這篇文章吧。
反轉(zhuǎn)一個單鏈表。
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
鏈表一般都是用迭代或是遞歸法來解決,而且一般都是構(gòu)造雙指針、三指針,比如反轉(zhuǎn)鏈表或是DP動態(tài)規(guī)劃。
我們可以申請兩個指針,第一個指針叫 pre,最初是指向 null 的。
第二個指針 cur 指向 head,然后不斷遍歷 cur。
每次迭代到 cur,都將 cur 的 next 指向 pre,然后 pre 和 cur 前進一位。
都迭代完了(cur 變成 null 了),pre 就是最后一個節(jié)點了。
java實現(xiàn)
class Solution {
public ListNode reverseList(ListNode head) {
//申請結(jié)點,pre和 cur,pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//記錄當前節(jié)點的下一個節(jié)點
tmp = cur.next;
//然后將當前節(jié)點指向pre
cur.next = pre;
//pre和cur節(jié)點都前進一位
pre = cur;
cur = tmp;
}
return pre;
}
}
Python實現(xiàn)
class Solution(object):
def reverseList(self, head):
if not head or not head.next:
return head
l = head
r = head.next
remain = r.next
l.next = None
while r:
r.next = l
l = r
r = remain
if remain:
remain = remain.next
return l
遞歸的兩個條件:
head.next.next = head
很不好理解,其實就是 head 的下一個節(jié)點指向head。遞歸函數(shù)中每次返回的 cur 其實只最后一個節(jié)點,在遞歸函數(shù)內(nèi)部,改變的是當前節(jié)點的指向。
class Solution {
public ListNode reverseList(ListNode head) {
//遞歸終止條件是當前為空,或者下一個節(jié)點為空
if(head==null || head.next==null) {
return head;
}
//這里的cur就是最后一個節(jié)點
ListNode cur = reverseList(head.next);
//如果鏈表是 1->2->3->4->5,那么此時的cur就是5
//而head是4,head的下一個是5,下下一個是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止鏈表循環(huán),需要將head.next設(shè)置為空
head.next = null;
//每層遞歸函數(shù)都返回cur,也就是最后一個節(jié)點
return cur;
}
}
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or head.next == None: return head
res = self.reverseList(head.next)
head.next.next = head
head.next = None
return res
以上是“LeetCode怎樣反轉(zhuǎn)鏈表”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。