題目描述

反轉(zhuǎn)一個(gè)單鏈表。

示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

解題思路

鏈表一般都是用迭代或是遞歸法來解決，而且一般都是構(gòu)造雙指針、三指針，比如反轉(zhuǎn)鏈表或是DP動(dòng)態(tài)規(guī)劃。

雙指針迭代

我們可以申請(qǐng)兩個(gè)指針，第一個(gè)指針叫 pre，最初是指向 null 的。

第二個(gè)指針 cur 指向 head，然后不斷遍歷 cur。

每次迭代到 cur，都將 cur 的 next 指向 pre，然后 pre 和 cur 前進(jìn)一位。

都迭代完了(cur 變成 null 了)，pre 就是最后一個(gè)節(jié)點(diǎn)了。

java實(shí)現(xiàn)

class Solution {
 public ListNode reverseList(ListNode head) {
  //申請(qǐng)結(jié)點(diǎn)，pre和 cur，pre指向null
  ListNode 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)指向pre
   cur.next = pre;
   //pre和cur節(jié)點(diǎn)都前進(jìn)一位
   pre = cur;
   cur = tmp;
  }
  return pre;
 }
}

Python實(shí)現(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

遞歸實(shí)現(xiàn)：

遞歸的兩個(gè)條件：

• 終止條件是當(dāng)前節(jié)點(diǎn)或者下一個(gè)節(jié)點(diǎn)==null
• 在函數(shù)內(nèi)部，改變節(jié)點(diǎn)的指向，也就是 head 的下一個(gè)節(jié)點(diǎn)指向 head 遞歸函數(shù)那句     head.next.next = head很不好理解，其實(shí)就是 head 的下一個(gè)節(jié)點(diǎn)指向head。

遞歸函數(shù)中每次返回的 cur 其實(shí)只最后一個(gè)節(jié)點(diǎn)，在遞歸函數(shù)內(nèi)部，改變的是當(dāng)前節(jié)點(diǎn)的指向。

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);
  //如果鏈表是 1->2->3->4->5，那么此時(shí)的cur就是5
  //而head是4，head的下一個(gè)是5，下下一個(gè)是空
  //所以head.next.next 就是5->4
  head.next.next = head;
  //防止鏈表循環(huán)，需要將head.next設(shè)置為空
  head.next = null;
  //每層遞歸函數(shù)都返回cur，也就是最后一個(gè)節(jié)點(diǎn)
  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