跳到主要内容

206. 反转链表(Easy)

题目描述​

反转一个单链表。

样例​

Input: 1->2->3->4->5->NULL
Ouptut: 5->4->3->2->1->NULL

题目解析​

解法一【双指针】【重点】【经典】

通过前后双指针的方法，是比较经典的用法，后面还会反复用到

解法二【递归】

代码​

双指针

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head 
        while cur:
            cur_next_bak = cur.next 
            cur.next = pre 
            # 向下一节点
            pre = cur
            cur = cur_next_bak
        return pre # 注意，最后返回的是 pre
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    pre, cur := nil, head 
    for cur != nil {
        next := cur.Next
        cur.Next = pre 

        pre = cur 
        cur = next 
    }
    return pre 
}

递归

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: # 走到最后一个节点
            return head 

        cur = self.reverseList(head.next)

        head.next.next = head 
        head.next = None # 为了解决第一个节点
        return cur